Re:Stack Overflow: the Blind Leading the Blind
by river_styx on Sunday August 31, 2008 @09:24PM
(#291627)
I must admit that I didn't understand his XOR solution. Can someone explain it?
[ Parent
| on HN ]
Suppose x = 0 and your list is [1,2,3,2,1]. If you xor 'x' with every number in your list then x = 1^2^3^2^1, which is the same as x = (1^1)^(2^2)^3 = 0^0^3 = 3. So, x=3 is the number that wasn't repeated. This works because a^b = b^a and a^a = 0.
Iterate through the list bitwise-XORing the numbers together into an accumulator. Because x ^ x = 0, and x ^ 0 = x, and ^ is commutative (x ^ y = y ^ x), the final value in the accumulator for a list like [x, y, y, x, z] is:
x ^ y ^ y ^ x ^ z
= x ^ x ^ y ^ y ^ z
= 0 ^ 0 ^ z
= z
Re:Stack Overflow: the Blind Leading the Blind
by brianr on Sunday August 31, 2008 @09:36PM
(#291636)
Here's an example in python:
>>> import random, operator
>>> nums = (range(5)*2)
>>> random.shuffle(nums)
>>> nums.pop()
1
>>> nums
[0, 4, 0, 3, 2, 4, 3, 1, 2]
>>> reduce(operator.xor, nums)
1
Re:Stack Overflow: the Blind Leading the Blind
by thorax on Sunday August 31, 2008 @09:52PM
(#291647)
To clarify for non-Pythoners/non-coders: If you assume "nums" already contains the list, most of his code above is setup. You only need these two lines of his code to get the answer:
import operator
answer = reduce(operator.xor, nums)