Question 15 : Find the number occurring odd number of times in an array

You are given an array of integers. All numbers occur even a number of times except one. You need to find the number which occurs an odd number of times. You need to solve it with o(n) time complexity and o(1) space complexity.

For example:

int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is : 50

Solution:

Solution 1: Use two for loops and compare elements:

This is a brute force solution for this problem but it takes o(n*n) time complexity.

Solution 2: Use Hashing

You can use the key as the number and count as a value and whenever a key is repeated, you can increment the counter by 1.

int getOddTimesElementHashing(int ar[]) 
{
    int i;
 
    HashMap<Integer,Integer> elements=new HashMap<Integer,Integer>();
    for (i = 0; i < ar.length; i++) 
    {
        int element=ar[i];
        if(elements.get(element)==null)
        {
            elements.put(element, 1);
 
        }
        else
            elements.put(element, elements.get(element)+1);
    }
    for (Entry<Integer,Integer> entry:elements.entrySet()) { 
        if(entry.getValue()%2==1)
        {
            return entry.getKey();
        }
 
    } 
    return -1;
}

but the above solution takes o(n) of space complexity.

Solution 3: Use XOR operation:

You can do a bitwise XOR operation for all elements and it will give you an element that occurs an odd number of times in the end.:

 int getOddTimesElement(int ar[]) 
  {
      int i;
      int result = 0;
      for (i = 0; i < ar.length; i++) 
      {
       result = result ^ ar[i];
      }
      return result;
  }

The above algorithms solve the problem with O(n) time complexity and o(1) space complexity and this is the best solution for the above program.

Java program to find the number occurring an odd number of times in an array::

 
public class NumberOddTimesMain 
{
    int getOddTimesElement(int ar[]) 
    {
        int i;
        int result = 0;
        for (i = 0; i < ar.length; i++) 
        {
            // XOR operation
            result = result ^ ar[i];
        }
        return result;
    }
 
    public static void main(String[] args) 
    {
        NumberOddTimesMain occur = new NumberOddTimesMain();
        int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
        System.out.println("Number which occurs odd number of times is : "+occur.getOddTimesElement(array));
    }
}

When you run the above program, you will get the below output::

Number which occurs odd number of times is : 50

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest