The problem
Exactly two numbers appear once and all others appear twice. Find the two single numbers.
Input: [1, 2, 1, 3, 2, 5] Output: [3, 5]
Picture it
Picture socks again, now with two loners. XOR of everything leaves a ^ b. Any switch that is on there is a position where a and b differ, so it splits all the socks into two piles, each containing one loner. XOR each pile separately.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
XOR all, pick a set bit, partition, XOR each group. O(n), O(1).
Python solution
def single_number(nums):
xor = 0
for x in nums:
xor ^= x # = a ^ b
low = xor & -xor # a switch where a and b differ
a = b = 0
for x in nums:
if x & low:
a ^= x
else:
b ^= x
return [a, b]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.