News for hackers. Stuff that matters.
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?
Re:Stack Overflow: the Blind Leading the Blind by adr on Sunday August 31, 2008 @09:31PM (#291630)
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.
Re:Stack Overflow: the Blind Leading the Blind by sah on Sunday August 31, 2008 @09:35PM (#291635)
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)