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));
    }
}

Python code 

def find_odd(arr):
    res = 0
    for num in arr:
        res ^= num
    return res
print(find_odd([2, 3, 2, 4, 4]))  # 3

  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      XOR method (bitwise)
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best & optimal
    
  

  

    

      HashMap frequency count
    
    

      O(n)
    
    

      O(n)
    
    

      Works but extra space
    
  

  

    

      Sorting then scan neighbors
    
    

      O(n log n)
    
    

      O(n)
    
    

      ❌ Slower & unnecessary