intro practice · coding problem
Find the single number (XOR)
Every element appears twice except one. Find it in O(n) time, O(1) space.
The mechanism
Bits give you three superpowers: a bitmask is an O(1) set, XOR cancels duplicates, and checking power-of-2 is a single AND. Two tricks worth memorizing: n & (n-1) clears the lowest set bit, and XOR-ing equal values gives zero.
Expected evidence
xor all → 2 for [4,1,2,1,4].
Try this drill in the practice workspace →
Hints when you need them
- a^a=0, a^0=a.
- XOR is commutative — order does not matter.