Where it runs
1. The problem
A warehouse scans every item twice: once on the way in, once on the way out. By evening the log holds every ID twice, except for one item that went missing: its ID appears only once. You need that single ID out of a million scans.
The safe answer is a map of counts: count every ID, then find the one with count 1. It works. But it needs O(n) memory to hold a million counts, just to find one number.
A few bit tricks do the same job in one line and O(1) memory. This lesson is about those tricks.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- find the single or unique number using XOR
- set, clear, toggle, or test a bit
- pack many yes/no flags into one integer
- count set bits or check a power of two
Looks similar, isn't
- Hash set / map
A set answers membership for any key at all. A bitmask does it for 32 known items, with no memory.
- Math and number theory (GCD, sieve, modular)
Both work on the number itself. That page is about divisors and primes, this one about bits.
- Backtracking
Subsets can be listed by counting from zero upward. Backtracking builds the same list recursively.
- Non-comparison sort (counting / radix)
Radix sort reads digits, sometimes as bits. Its goal is grouping, never flipping.
One operation is O(1) on a 32-bit value. Looping the bits is O(32), which counts as constant.
On LeetCode
Problems where one number is missing or left without a pair, and quick tests on the lowest bit. XOR cancels equal numbers, x & (x-1) clears the lowest 1 bit, and x & -x keeps only that bit.
The lesson's findUnique. XOR everything, and each pair cancels to 0.
A power of two has exactly one 1 bit, so n is above 0 and n & (n-1) is 0.
XOR every index from 0 to n with every number, and the missing number is what stays.
XOR everything to get a XOR b, take its lowest bit with x & -x, and split the numbers into two groups by that bit.
Count each of the 32 bits across all numbers, and the bits whose count does not divide by 3 belong to the single number.