Find two elements in an array, which occurs exactly once

user_10962180 0
Viewed 610

Recently I was given the following task:

Suppose you're given an array of elements of length N where every element except for two special, which appears once, occurs exactly twice. Find this special numbers.

I also know that every element in array is non-negative and is not more than 10^9 and the length of the array, N is less than or equal to 10^6

I think that the solution is using xors. Here is my thoughts:

Let's xor all elements in array. Since xor is commutative, e.g. xor(a, b)=xor(b, a), we can conclude that all elements which occurs twice will be zeroed:

xor(a, b, a, c)=xor(a, a, b, c)=xor(xor(a, a), b, c)=xor(0, b, c)=xor(b, c)

And then xoring whole array we'll get the xor of our two special elements. What to do next? Maybe, some other solutions?

P.S. Please, don't tell me anything about hash tables. Firstly, I've tried it, but it didn't work, since my hash functions were not able to compress all range of numbers into array with any reasonable size(for my machine at least). Secondly, it is prohibited by task's condition.

EDIT: My bad, I didn't mention that sorted is also prohibited.

xor c algorithm
1 Answers

Xoring in good approach.

Just think - what is result of xoring all elements? As you wrote, all paired elements are zeroed, so result is

 R = A xor B

Consider one bits of result R - we can see that they correspond to distinct bits of A and B.

So we can choose any non-zero bit of R, and make the second run - but xor only elements having this bit non-zero.

Now we have new result - it is equal or A either B.

Calculating the second one is elementary: B = R xor A

Complexity remains linear O(n)

user_8444160
Related