Hacker News Reader

Comment by ardit33 | Hacker News Reader

Interesting post. I agree with this, and I see at work often. The blind leading the blind, especially when you have new people in the team comming in. A smart newcomer will eventually realise the advice they are getting is not good, and move on to somebody else.

"What would be the best algorithm for finding a number that occurs only once in a list which has all other numbers occurring exactly twice. So, in the list of integers (lets take it as an array) each integer repeats exactly twice, except one. To find that one, what is the best algorithm."

I want the hacker community to answer this question (which seems more like a typical interview question). Ideas?

View on HN

First thing that came to mind for me (just assuming there was needed a practical way to do it) was the following (translated into Python):

  # associative array / dict / hash
  store = {}
  for elem in inputlist:
    if elem in store:
      del store[elem]
    else:
      store[elem] = True
  # return the only key left
  return store.keys()[0]

Now that I've looked at the post, the XOR approach is quite efficient and a more fun answer.

I must admit that I didn't understand his XOR solution. Can someone explain it?

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

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

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)

What are the constraints? If it's processing time or memory, I'd choose the XOR solution (which is brilliant). But it could also be the time to solve the problem. This would mean that the first working solution that comes to mind would be the best. Or the solution should be transparent to non-programmers, which probably eliminates the XOR hack. It could also be the joy while coding...

Reply on news.ycombinator.com