Find the two non repeating numbers.

Problem Statement:

You are given an array of repeating numbers(twice), but two numbers are not repeating.
You need to find out those numbers.

Example

Input: {1, 1, 2, 3, 2, 3, 4, 5}

Output: 4, 5

Solution

The solution is very simple. Below are the steps we use to achieve the solution.

We use XOR for the solution.

XOR of same elements is 0.

And in our array, WKT all the elements that are repeated, are only twice.

Hence XOR of all the repeated elements will cancel out each other.

Then the result will be X XOR Y, since X and Y are not repeating.

Now we need to find 2 elements in that array. For that we will divide the array in to 2 parts.

We divide the array based on if, kth bit is set to 1 and second group has the ele­ment for which the kth bit is 0.

Hence XOR all the ele­ment whose kth bit is set will pro­duce either X or Y.
Hence XOR all the ele­ment whose kth bit is not will pro­duce either X or Y.

To get the rightmost set bit of the result, we use below formula:

N & ~ (N -1)

Time complexity: O(n)

Example:

Consider the array {2, 3, 1, 3, 2, 7}

XOR of the array = 110 in binary = 1101110

Now the rightmost set bit of the result “110” is 2nd bit form right.

Now we divide the array based on, if the 2nd bit is set or not as shown below:

2 = 1 0 1
3 = 0 1 1
1 = 0 0 1
2 = 1 0 1
3 = 0 1 1
7 = 1 1 1

From the above binary format, the elements {2, 3, 7} have their 2nd bit set. Hence they are in one group.

The element {1} does not have 2nd bit set. Hence it is in one group.

Now we XOR all the elements from group 1 and group 2 separately to get the result.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;


void get_2_non_repeated_numbers(int *arr, int len)
 {

     int Xor = arr[0];
     for (int i = 1; i < len ; i++) 
     {
         Xor ^= arr[i];
     }

     int right_most_set_bit = Xor & ~ (Xor -1);

     //divide the array elements into 2 groups
     int a = 0;
     int b = 0;
     for (int i = 0; i < len ; i++) 
     {
         int x = arr[i];
         if((x & right_most_set_bit)!=0)
             a ^= x;
         else
             b ^= x;
     }
     cout<<"Non Repeating Elements are: " << a<< " and " << b<<endl;
 }
int main() 
{ 
   int arr[] = {2, 3, 2, 3, 4, 6, 7, 6, 7, 8};
   get_2_non_repeated_numbers (arr, 10);

    return 0; 
} 

Output:

Non Repeating Elements are: 4 and 8