XOR Pairing (Single Number)
XOR everything. Duplicates cancel and the unpaired value remains.
XOR Tricks: Find the single number
0 xor 4 = 4. First time 4 appears, so its bits are folded in.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Taught by the same lesson
XOR Tricks covers these too, in the same run.