Every number appears twice except one. XOR them all together: pairs cancel to zero, and the loner is all that's left.
▼The problem
LeetCode 136 (Easy). Every element of a non-empty list appears exactly twice except one, which appears once. Find that one in linear time using only constant extra space.
Example: [4, 1, 2, 1, 2] → 4.
The solution
def singleNumber(nums):
x = 0
for n in nums:
x ^= n # pairs cancel
return x # the singleTranscript
Single Number. Every number in the list appears twice, except one. Find the one without a partner, using linear time and only constant extra space.
Take four, one, two, one, two. The ones pair up, the twos pair up, and four is left dancing alone. The answer is four.
The obvious way is a coat check: a set of the numbers you've seen. When a number arrives, add it. When its partner shows up, remove it. Whatever is left at the end is the answer. That's linear time, but the set can hold half the list, so the space grows with the input.
The trick is XOR. Write the numbers in binary and compare them bit by bit: matching bits give zero, different bits give one. So x XOR x is zero, and x XOR zero is x. And the order doesn't matter. XOR the whole list together: every pair cancels, and only the single number is left.
In code, start a variable at zero, XOR in every number, and return it. No set, just one number.
Watch the floor tiles: four, two and one. Four steps on and lights the four tile: one, zero, zero. One lights the one tile: five. Two lights the two tile: seven. Then the second one arrives, its tile goes dark, and the pair leaves: six. The second two does the same: four. Only four is still dancing.
One XOR per number, so the time is linear. One variable, so the extra space is constant.
Pairs cancel, the single stays. That's Single Number.