3 ms·
I must admit that I didn't understand his XOR solution. Can someone explain it?
by river_styx 18y ago
I 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)