Find the two non-repeating elements in an array of repeating elements | GeeksforGeeks

Find the two non-repeating elements in an array of repeating elements | GeeksforGeeks
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.

First calculate the XOR of all the array elements.

All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. 

So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. 

Let us see an example.
   arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
     xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.   
   Since we can easily get the rightmost set bit, let us use it.
     set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
   Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of         
   elements in each set, and we get the non-repeating 
   elements 7 and 9. Please see implementation for this   
   step.

void get2NonRepeatingNos(int arr[], int n, int *x, int *y)

{

  int xor = arr[0]; /* Will hold xor of all elements */

  int set_bit_no;  /* Will have only single set bit of xor */

  int i;

  *x = 0;

  *y = 0;

  /* Get the xor of all elements */

  for(i = 1; i < n; i++)

   xor ^= arr[i];

  /* Get the rightmost set bit in set_bit_no */

  set_bit_no = xor & ~(xor-1);

  /* Now divide elements in two sets by comparing rightmost set

   bit of xor with bit at same position in each element. */

  for(i = 0; i < n; i++)

  {

    if(arr[i] & set_bit_no)

     *x = *x ^ arr[i]; /*XOR of first set */

    else

     *y = *y ^ arr[i]; /*XOR of second set*/

  }

}

http://yuanhsh.iteye.com/blog/2185914




1. public void findTwoUniqueNumbers(int[] A) {  
2.     int x = 0;  
3.     for(int i=0; i<A.length; i++) {  
4.         x ^= A[i];  
5.     }  
6.     int lsb = x & -x;  
7.     int a = 0, b = 0;  
8.     for(int i=0; i<A.length; i++) {  
9.         if((A[i]&lsb) == lsb) {  
10.             a ^= A[i];  
11.         } else {  
12.             b ^= A[i];  
13.         }  
14.     }  
15.     System.out.println("a="+a + ", b="+b);  
16. } 

Read full article from Find the two non-repeating elements in an array of repeating elements | GeeksforGeeks