Re:Stack Overflow: the Blind Leading the Blind
by thorax on Sunday August 31, 2008 @09:35PM
(#291634)
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.
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?
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)
Re:Stack Overflow: the Blind Leading the Blind
by gopher on Monday September 01, 2008 @12:03PM
(#291956)
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...
"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?