Say we Have n distinct numbers


And we xor the result

xoredResult = x1^x2...^xn

And if we AND(&) with one of the number say x2 We get Zero

xoredResult & x2 = 0

Can we always claim that if the ANDed result is zero that the number is repeated ? Can this be used to find the first repeated element in a stream of numbers ?

  • $\begingroup$ You are saying that $(a \oplus b) \wedge b = 0$ if $a = 0$ and $b=1$ then the output is 1 $\endgroup$ – kelalaka Dec 23 '19 at 20:12

It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers contains.

Or for an other example, the set { 1, 2, 3 } xors to zero (so it ANDed by any of its members, or even anything else, yields zero) but contains no repeated elements.

| cite | improve this answer | |

Of course not.

Take x = 110, y = 101, z = 011. Every bit is set in two numbers, so r = (x xor y xor z) = 0. So x and r, y and r, z and r are all zero, with nothing repeated.

The code you linked to is something totally different. There each number occurs 3 times, except one number X which occurs once. If we count how often each bit is set, then for a bit in X the number of times it is set is 3k+1, for a bit not in X the number of times it is set is 3k times for unknown k.

The code there simulates n counters modulo 3 with bit operations. Totally different. Very clever method. Can be generalised to "for every number except at most one, the number of occurences is a (modulo b) for fixed a and b. Find the value of the one number where the number of occurences is not a (modulo b) or show there is none", running in O (n log b) time.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.