5 ms·
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 smar
by ardit33 18y ago
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?
- river_styx 18y agoI must admit that I didn't understand his XOR solution. Can someone explain it?
- deleted 18y ago[deleted]
- adr 18y agoSuppose 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.
- sah 18y agoIterate 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
- brianr 18y agoHere'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
- thorax 18y agoTo 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)
- thorax 18y agoFirst 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.
- deleted 18y ago[deleted]
- gopher 18y agoWhat 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...