CareerCup

Taken from geeksforgeeks

#include <stdio.h>;
#include <stdlib.h>;
 
/* This finction sets the values of *x and *y to nonr-epeating
 elements in an array arr[] of size n*/
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*/
  }
}     
 
/* Driver program to test above function */
int main()
{
  int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
  int *x = (int *)malloc(sizeof(int));
  int *y = (int *)malloc(sizeof(int));
  get2NonRepeatingNos(arr, 8, x, y);
  printf(" The non-repeating elements are %d and %d";, *x, *y);
  getchar();
}

I am going to try explain this more clearly.

First how xor works: if you have two numbers say 10 (1010) and 8 (1000), xor operation ( done using operator ^ ) will return the bits which are set in one number but not in the other.

10 -- 1010
08 -- 1000
---------------
^ -- 0010
---------------
Here the third bit is set(from right) in 10 but not in 8;

Now the problem states that there are 2n + 2 numbers such that n numbers are repeated.
eg. for n = 3: { 2, 3, 2, 4, 5, 4, 5, 6 }
there are two of ( 2, 4 & 5 ) but only one of ( 3 & 6 )

Lets take the first set of number that repeats..
when we xor a number with itself the result is zero.
2 ^ 2 = 0 (in binary: 10 ^ 10 )
4 ^ 4 = 0
5 ^ 5 = 0

Now we have actually got rid of the numbers that repeats twice.

so when we xor all the elements of the array : a[i] ^ a[i+1] ^ ... a[n], we would have performed, for the above example ( 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 4 ^ 5 ^ 6 )
Since the repeating elements are nullified :) we are left with ( 3 ^ 6 ), the xor of the two elements we need to find. If the elements are equal, the 2n+2 constraint is not valid and hence these two numbers would have also been nullified.

Now all we have to do is extract the two numbers (x, y) from ( 3 ^ 6 )

3 ^ 6 is
011
110
-----
101
-----
what we can infer from the above is that the last bit is set in one number and not in the other. ( and so does the first bit)

set_bit_no = xor & ~(xor-1);
This line in the above example by Rajat Rastogi can be replaced with

int set_bit_no = 1;
while ( ! ( xor & set_bit_no ) )
set_bit_no <<=1;

what it does is right shift, a bit at a time and check whether it is set in the result of ( 3 ^ 6 )
Why do we need this?

Because, when doing a xor, a bit is set only when it is set in one and not in the other. So we are actually isolating a trait of one number so that we can extract it from the result.

Now is the tricky part.

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

}

Our example array: { 2, 3, 2, 4, 5, 4, 5, 6 }
x & y is initially zero;

Again we apply the same principle, but this time we check whether the rightmost bit in set in one each element of the array..if its set, it will be removed when a pair of the same item is encountered and thus we will be able to extract x;

Then we also xor the elems which does not have the right most bit set. So, we will be extracting all the pairs with this bit not set and y ( the pairs cancel each other and y remains )

I have one other solution for it -

We can use hash to solve it. Here we have to choose the hash function carefully..

find_duplicate()
{
let i = 0
compute x = hash(a[i])
if(a[i] == a[hash])
{ i++ }
else
{ swap(a[0],a[x]) }
if (i <= n)
{ call find_duplicate(i) }
else
{ return i}
}

This will find the element required for the first case.
If we now run the same algo for another n times it will find the 2nd element too.
I do not believe it to be faster than Xor algo. It's beautiful.

God like...

Could someone explain about set_bit_no concept. Its not very clear to me.

Got it.

I got it.

for the same pair of number a, we have a^a = 0. Therefore, for N pairs, like a,b,c...a,b,c..., we still have a^b^c^...^a^b^c^...=0.

So if we have 2N+1 numbers with N pairs, the result of xor up all the number is the unrepeated one. If we have 2N+2 with N pairs and unrepeated number x y, the result = x^y and for sure result > 0. Then we split the numbers into two groups, to extract x and y respectively.

Awesomly awesome..!

I am going to try explain this more clearly.

First how xor works: if you have two numbers say 10 (1010) and 8 (1000), xor operation ( done using operator ^ ) will return the bits which are set in one number but not in the other.

10 -- 1010
08 -- 1000
---------------
^ -- 0010
---------------
Here the third bit is set(from right) in 10 but not in 8;

Now the problem states that there are 2n + 2 numbers such that n numbers are repeated.
eg. for n = 3: { 2, 3, 2, 4, 5, 4, 5, 6 }
there are two of ( 2, 4 & 5 ) but only one of ( 3 & 6 )

Lets take the first set of number that repeats..
when we xor a number with itself the result is zero.
2 ^ 2 = 0 (in binary: 10 ^ 10 )
4 ^ 4 = 0
5 ^ 5 = 0

Now we have actually got rid of the numbers that repeats twice.

so when we xor all the elements of the array : a[i] ^ a[i+1] ^ ... a[n], we would have performed, for the above example ( 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 4 ^ 5 ^ 6 )
Since the repeating elements are nullified :) we are left with ( 3 ^ 6 ), the xor of the two elements we need to find. If the elements are equal, the 2n+2 constraint is not valid and hence these two numbers would have also been nullified.

Now all we have to do is extract the two numbers (x, y) from ( 3 ^ 6 )

3 ^ 6 is
011
110
-----
101
-----
what we can infer from the above is that the last bit is set in one number and not in the other. ( and so does the first bit)

set_bit_no = xor & ~(xor-1);
This line in the above example by Rajat Rastogi can be replaced with

int set_bit_no = 1;
while ( ! ( xor & set_bit_no ) )
set_bit_no <<=1;

what it does is right shift, a bit at a time and check whether it is set in the result of ( 3 ^ 6 )
Why do we need this?

Because, when doing a xor, a bit is set only when it is set in one and not in the other. So we are actually isolating a trait of one number so that we can extract it from the result.

Now is the tricky part.

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

}

Our example array: { 2, 3, 2, 4, 5, 4, 5, 6 }
x & y is initially zero;

Again we apply the same principle, but this time we check whether the rightmost bit in set in one each element of the array..if its set, it will be removed when a pair of the same item is encountered and thus we will be able to extract x;

Then we also xor the elems which does not have the right most bit set. So, we will be extracting all the pairs with this bit not set and y ( the pairs cancel each other and y remains )

I am going to try explain this more clearly.

First how xor works: if you have two numbers say 10 (1010) and 8 (1000), xor operation ( done using operator ^ ) will return the bits which are set in one number but not in the other.

10 -- 1010
08 -- 1000
---------------
^ -- 0010
---------------
Here the third bit is set(from right) in 10 but not in 8;

Now the problem states that there are 2n + 2 numbers such that n numbers are repeated.
eg. for n = 3: { 2, 3, 2, 4, 5, 4, 5, 6 }
there are two of ( 2, 4 & 5 ) but only one of ( 3 & 6 )

Lets take the first set of number that repeats..
when we xor a number with itself the result is zero.
2 ^ 2 = 0 (in binary: 10 ^ 10 )
4 ^ 4 = 0
5 ^ 5 = 0

Now we have actually got rid of the numbers that repeats twice.

so when we xor all the elements of the array : a[i] ^ a[i+1] ^ ... a[n], we would have performed, for the above example ( 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 4 ^ 5 ^ 6 )
Since the repeating elements are nullified :) we are left with ( 3 ^ 6 ), the xor of the two elements we need to find. If the elements are equal, the 2n+2 constraint is not valid and hence these two numbers would have also been nullified.

Now all we have to do is extract the two numbers (x, y) from ( 3 ^ 6 )

3 ^ 6 is
011
110
-----
101
-----
what we can infer from the above is that the last bit is set in one number and not in the other. ( and so does the first bit)

set_bit_no = xor & ~(xor-1);
This line in the above example by Rajat Rastogi can be replaced with

int set_bit_no = 1;
while ( ! ( xor & set_bit_no ) )
set_bit_no <<=1;

what it does is right shift, a bit at a time and check whether it is set in the result of ( 3 ^ 6 )
Why do we need this?

Because, when doing a xor, a bit is set only when it is set in one and not in the other. So we are actually isolating a trait of one number so that we can extract it from the result.

Now is the tricky part.

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

}

Our example array: { 2, 3, 2, 4, 5, 4, 5, 6 }
x & y is initially zero;

Again we apply the same principle, but this time we check whether the rightmost bit in set in one each element of the array..if its set, it will be removed when a pair of the same item is encountered and thus we will be able to extract x;

Then we also xor the elems which does not have the right most bit set. So, we will be extracting all the pairs with this bit not set and y ( the pairs cancel each other and y remains )

I am going to try explain this more clearly.

First how xor works: if you have two numbers say 10 (1010) and 8 (1000), xor operation ( done using operator ^ ) will return the bits which are set in one number but not in the other.

10 -- 1010
08 -- 1000
---------------
^ -- 0010
---------------
Here the third bit is set(from right) in 10 but not in 8;

Now the problem states that there are 2n + 2 numbers such that n numbers are repeated.
eg. for n = 3: { 2, 3, 2, 4, 5, 4, 5, 6 }
there are two of ( 2, 4 & 5 ) but only one of ( 3 & 6 )

Lets take the first set of number that repeats..
when we xor a number with itself the result is zero.
2 ^ 2 = 0 (in binary: 10 ^ 10 )
4 ^ 4 = 0
5 ^ 5 = 0

Now we have actually got rid of the numbers that repeats twice.

so when we xor all the elements of the array : a[i] ^ a[i+1] ^ ... a[n], we would have performed, for the above example ( 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 4 ^ 5 ^ 6 )
Since the repeating elements are nullified :) we are left with ( 3 ^ 6 ), the xor of the two elements we need to find. If the elements are equal, the 2n+2 constraint is not valid and hence these two numbers would have also been nullified.

Now all we have to do is extract the two numbers (x, y) from ( 3 ^ 6 )

3 ^ 6 is
011
110
-----
101
-----
what we can infer from the above is that the last bit is set in one number and not in the other. ( and so does the first bit)

set_bit_no = xor & ~(xor-1);
This line in the above example by Rajat Rastogi can be replaced with

int set_bit_no = 1;
while ( ! ( xor & set_bit_no ) )
set_bit_no <<=1;

what it does is right shift, a bit at a time and check whether it is set in the result of ( 3 ^ 6 )
Why do we need this?

Because, when doing a xor, a bit is set only when it is set in one and not in the other. So we are actually isolating a trait of one number so that we can extract it from the result.

Now is the tricky part.

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

}

Our example array: { 2, 3, 2, 4, 5, 4, 5, 6 }
x & y is initially zero;

Again we apply the same principle, but this time we check whether the rightmost bit in set in one each element of the array..if its set, it will be removed when a pair of the same item is encountered and thus we will be able to extract x;

Then we also xor the elems which does not have the right most bit set. So, we will be extracting all the pairs with this bit not set and y ( the pairs cancel each other and y remains )

I am going to try explain this more clearly.

First how xor works: if you have two numbers say 10 (1010) and 8 (1000), xor operation ( done using operator ^ ) will return the bits which are set in one number but not in the other.

10 -- 1010
08 -- 1000
---------------
^ -- 0010
---------------
Here the third bit is set(from right) in 10 but not in 8;

Now the problem states that there are 2n + 2 numbers such that n numbers are repeated.
eg. for n = 3: { 2, 3, 2, 4, 5, 4, 5, 6 }
there are two of ( 2, 4 & 5 ) but only one of ( 3 & 6 )

Lets take the first set of number that repeats..
when we xor a number with itself the result is zero.
2 ^ 2 = 0 (in binary: 10 ^ 10 )
4 ^ 4 = 0
5 ^ 5 = 0

Now we have actually got rid of the numbers that repeats twice.

so when we xor all the elements of the array : a[i] ^ a[i+1] ^ ... a[n], we would have performed, for the above example ( 2 ^ 3 ^ 2 ^ 4 ^ 5 ^ 4 ^ 5 ^ 6 )
Since the repeating elements are nullified :) we are left with ( 3 ^ 6 ), the xor of the two elements we need to find. If the elements are equal, the 2n+2 constraint is not valid and hence these two numbers would have also been nullified.

Now all we have to do is extract the two numbers (x, y) from ( 3 ^ 6 )

3 ^ 6 is
011
110
-----
101
-----
what we can infer from the above is that the last bit is set in one number and not in the other. ( and so does the first bit)

set_bit_no = xor & ~(xor-1);
This line in the above example by Rajat Rastogi can be replaced with

int set_bit_no = 1;
while ( ! ( xor & set_bit_no ) )
set_bit_no <<=1;

what it does is right shift, a bit at a time and check whether it is set in the result of ( 3 ^ 6 )
Why do we need this?

Because, when doing a xor, a bit is set only when it is set in one and not in the other. So we are actually isolating a trait of one number so that we can extract it from the result.

Now is the tricky part.

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

}

Our example array: { 2, 3, 2, 4, 5, 4, 5, 6 }
x & y is initially zero;

Again we apply the same principle, but this time we check whether the rightmost bit in set in one each element of the array..if its set, it will be removed when a pair of the same item is encountered and thus we will be able to extract x;

Then we also xor the elems which does not have the right most bit set. So, we will be extracting all the pairs with this bit not set and y ( the pairs cancel each other and y remains )

can genius write a code for this.
I could not solve it when both non repeating numbers are either odd or even.
thanks in advance.

I have idea to solve this but this contain extra space and my algo is limit to 0-9 number and this code can check to n no of time number not repeated

b[10]={0,0,0,0,0,0,0,0,0,0}//Storing initial value to it for(i=0;i<array.length;i++)
{
if(b[array[i]])
{
  b[array[i]]=b[array[i]]-array[i];//subtracting number if it is repeated
}
else
b[array[i]]=array[i];//storing value in array
 }
for(i=0;i<10;i++)
{
  if(b[i])
  printf("%d",b[i]);
}

If we can use extra memory, then using hashmaps we can do it. For each element we add hash(array[i])=1; and whenever we find containsKey(array[i])..we delete it so that at the end of scanning all the elements in array in hashmap we will be left with only one element.

If he asks for 2 or more, then all the remaining elements in the map are unique.