(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.

example :

Arr = [1,2,3,1] => 2, 3 occurring once

Arr = [2, 3, 7, 9, 11, 2, 3, 11] => 7, 9 occurring once

If only one element is occurring once we can easily find the one.

by XORing all. ( Same number will results in 0 while XOR so last element is remaining)

Now as we have question with two such number, we need to find logic.

**Method 1) Brute force** : Loop O(n^2) to check each element occur twice or not.

**Method 2) Sorting** : Sort all elements , so we can find all repeating numbers together. and count occurrence.

**Method 3) Using Hashing** : Crate Hash of each element and count. map<element, count> so after one iteration map will contain <(2,2) , (3,2) , (7,1), (9,1), (11,2) >

Now traverse map and find element whose count is 1.

**Method 4) Using Bit Logic : **Logic given below

XOR of two same numbers results in 0

XOR of two different numbers x and y results in a number which contains set bits at the places where x and y differ.

x and y are 10 ( 0100 ) and 11 ( 1001 ), then result x XOR y would be 01 ( 1101 )

Idea is to XOR all the elements in set.

In the result xor, all repeating elements would nullify each other.

The result would contain the set bits where two non-repeating elements differ.

2, 3, 7, 9, 11, 2, 3, 11 Result Xor will contain XOR of 7 and 9 = 14

(0111 XOR 1001 = 1110)

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, if we take any set bit of the result xor (set_bit_no) and again do XOR of the subset where that particular bit is set, we get the one non-repeating element. And for other non-repeating element we can take the subset where that particular bit is not set.

**first subset** will be of numbers where number AND set_bit_no is non zero (to find particular bit is set)

**second subset** where number AND set_bit_no is zero ( particular bit is not set )

so do…

if(arr[i] & set_bit_no)

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

else

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

Now X and Y contain non repeating elements…

Code : http://ideone.com/MA4IYR

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

{

int xor = arr[0];

int set_bit_no;

int i;

*x = 0;

*y = 0;

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

xor ^= arr[i];

set_bit_no = xor & ~(xor-1);

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*/

}

}