Find the number occurring odd number of times in an array

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to find number occurring odd number of times in the array.

Problem:

You are given a array of integer. All numbers occur even number of times except one. You need to find the number which occurs odd number of time. 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 brute force solution for this problem but it takes o(n*n) time complexity.

Solution 2 : Use Hashing

You can use key as number and count as value and whenever key is repeated , you can increment 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 above solution takes o(n) of space complexity.

Solution 3: Use XOR operation: 

You can do bitwise XOR operation for all elements  and it will give you element which occurs 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;
  }
Above algorithms solves the problem with O(n) time complexity and o(1) space complexity and this is best solution for above program.

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

package org.arpit.java2blog;

//Java program to find the element occurring odd number of times

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 above program, you will get below output:
Number which occurs odd number of times is : 50

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012