Bit manipulationbit-single-number
Lesson·difficulty 3/5·~15 min
Bits: the single number
Bits: the single number
Every value in the list appears exactly twice, except one value that appears once. Find that lonely value.
You could count occurrences with a dictionary, but there's a slicker trick using
the XOR operator ^. XOR has two magic properties:
python
x ^ x == 0 # anything XOR'd with itself cancels to 0
x ^ 0 == x # XOR with 0 leaves a value unchanged
XOR is also commutative and associative, so the order doesn't matter. If you
XOR the whole list together, every pair cancels to 0, and the single value is
all that survives:
python
2 ^ 2 ^ 1 == (2 ^ 2) ^ 1 == 0 ^ 1 == 1
This runs in one pass with no extra memory.
Your task
Write single_number(nums) returning the one value that appears only once.
python
single_number([2, 2, 1]) # 1
single_number([4, 1, 2, 1, 2]) # 4
single_number([7]) # 7
Hint: start an accumulator at 0 and XOR every element into it.
Tests
- lonely one
- lonely four
- single element
- lonely zero
- larger list (hidden)
Stuck? Ask for a spark
warming up
Loading editor…
$ Console output will appear here.