techInterview Discussion

Hello,

I recently encountered this question in an interview and answered it properly. As I have gained so much from this forum , I just wanted to share this question, which might help other aspirants.

There is an array with 2n+1  numbers and all the numbers are present two times except one , find that unique number ?

I remember that XOR is handy for this.

integer xoring=0
for i=1 to 2n+1
  xoring=xoring xor thearray[i]
print xoring    // This is the one-occurrence value.

Sincerely,

Gene Wirchenko

This is a common interview trick.

One variant of this question is, where,
the numbers are sorted and you have to find the unique entry in log(n) time.[as opposed to O(n) time for XORing]

It relies on the property that there should be same number on the odd position *and* even position; after passing the unique number, the same number is on even and odd position.