Find the two Numbers with Odd Occurrences in an Unsorted Array

Difficulty Level Easy
Frequently asked in Accolite Factset Google Oracle
ArrayViews 2283

Problem Statement

In the “Find the two Numbers with Odd Occurrences in an Unsorted Array” problem we have given an unsorted array. In this array other than two numbers all other numbers occur even number of times. Find the two numbers that occur an odd number of times.

Note: The array should contain exactly two numbers that occur an odd number of times

Input Format

The first and only one line containing an integer n.

Second-line containing n space-separated integers.

Output Format

The first and only one line containing two integers with space-separated.

Example

5 5 4 6 6 7
4 7

Explanation: The main idea is using bitwise XOR. For example, XOR of 4 and 7 is 4(100) ^ 7(111) = 011.

Properties of XOR

i) XOR of any number with itself gives 0 ie, x ^ x = 0
ii) XOR of any number with 0 gives us the number ie, x ^ 0 = x

Algorithm to Find the two Numbers with Odd Occurrences in an Unsorted Array

Given an array of numbers that is unsorted. All the numbers occur an even number of times except two which occur an odd number of times. Let the two numbers be a and b which occurs an odd number of times, Take xor of all the elements of the array and store it in a variable. This will give xor of a and b . Since all other elements occur even number of times and xor of number with itself is zero.

Suppose we have an array [2,2,5,4,6,6]. Xor of all elements = 5^4.

Now we see that after taking the xor of all the elements, the set bit in the xor tells that at this position either number a has set a bit or b has set bit. Since this case only leads to a set bit in the output at this position. So, every set bit in the final xor of all the elements represents that the corresponding bit in a and b are different.

Xor of 5(101) and 4(100) is (001). We see that the leftmost bit is different in both the numbers. So we can use this concept to solve this problem. We take a set bit in the xor. Let suppose we take the rightmost set bit of the xor. And we take two variables to store the two numbers. Divide all the elements of the array in two sets, first the element having the corresponding bit set and second,the elements having the corresponding bit unset.

[2,2,5,4,6,6]

Number with Right most bit set (001). 

The two sets are – 

  1. [ 5]
  2. [2,2,4,6,6]

After taking xor of all elements in both sets we get the two numbers that occur an odd number of times. We get 5 and 4 after taking xor of all elements in these sets. For getting the number with a rightmost set bit – 

We first remove the rightmost set bit and then xor with the number, then we get the numbers with the rightmost set bit. To remove rightmost set bit – a&(a-1).

Implementation

C++ Program to Find the two Numbers with Odd Occurrences in an Unsorted Array

#include <bits/stdc++.h>
using namespace std;

vector<int> two_odd_occuring_elements(vector<int> a, int n)  {
    int xr=0;
    for(int i=0;i<n;i++){
        xr^=a[i];
    }
    int one=0,two=0;
    xr = xr^(xr&(xr-1));
    for(int i=0;i<n;i++){
        if((xr&a[i])==0){
            one^=a[i];
        }else{
            two^=a[i];
        }
    }
    return {one,two};
}

int main() {
  int n;
  cin>>n;
  vector<int> v;
  for(int i=0;i<n;i++){
    int x;cin>>x;
    v.push_back(x);
  }
  vector<int> ans = two_odd_occuring_elements(v,n);
  cout<<ans[0]<<" "<<ans[1]<<endl;
  
  return 0;
}

Java Program to Find the two Numbers with Odd Occurrences in an Unsorted Array

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        two_odd_occuring_elements(arr,n);
  }
  
  public static void two_odd_occuring_elements(int[] a,int n){
        int xr=0;
        for(int i=0;i<n;i++){
          xr^=a[i];
      }
      int one=0,two=0;
      xr = xr^(xr&(xr-1));
      for(int i=0;i<n;i++){
          if((xr&a[i])==0){
              one^=a[i];
          }else{
              two^=a[i];
          }
      }
      System.out.print(one+" "+two+"\n");
    }
    
    public static void swap(int a, int b) 
    { 
        int temp = a; 
        a = b; 
        b = temp; 
    } 

}
8
4 2 4 5 2 3 3 1
1 5

Complexity Analysis to Find the two Numbers with Odd Occurrences in an Unsorted Array

Time Complexity

O(n) where n is the size of the given array. Here we traverse the whole array element by element and perform some task in constant time.

Space Complexity

O(1) because we don’t create any auxiliary space here.

Translate »