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