Predict the output
What does this print?
from functools import reduce
from operator import xor
print(reduce(xor, [4, 1, 2, 1, 2]), 5 ^ 5, 7 ^ 0)Choose an answer, then open Show answer below to check it.
Answer: A 4 0 7
Right: the pairs of 1 and 2 cancel, x ^ x is 0, and x ^ 0 is x.
Because order does not matter for XOR, the pairs can sit anywhere in the list and still cancel.
XOR all the values. XOR is associative and commutative, x ^ x = 0 and x ^ 0 = x, so every pair cancels and only the unpaired value remains. O(n) time, O(1) memory.
Explain finding the unpaired value with XOR.
Say your answer out loud, then check which of these points you covered:
XOR as 'cancel pairs' is the bit-trick template.
A set or Counter works in O(n) memory and is a fine first answer.
With two unpaired values, split by any bit where their XOR is 1 and XOR each group.
def unpaired(vals: list[int]) -> int:
acc = 0
for v in vals:
acc ^= v # equal pairs cancel to 0
return accfun unpaired(vals: List<Int>): Int {
var acc = 0
for (v in vals) acc = acc xor v // equal pairs cancel to 0
return acc
}Name the three XOR rules out loud; the answer follows from them.
Think of your answer first, then open the hint.
What if every other value appears three times?
Count each bit position modulo 3 across all values.
How do you find two unpaired values?
XOR all to get a ^ b, take its lowest 1 bit, and XOR the two groups split by that bit.
What each operation costs: Hash Functions
From the author
Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.
Suggest a fix if something here is wrong or out of date.