Pattern 4: The power of XOR
XOR (
^) has an almost magical property that solves a whole family of "find what's left" problems in O(n) time and O(1) space — no hash map, no sorting.
Try it first: Missing Number
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Given an array nums with n distinct numbers taken from 0..n, one number is missing. Find it. Try to do it in O(n) time and O(1) extra space.
Example: nums = [3, 0, 1] (should have 0,1,2,3) → 2 is missing.
Tried it? You probably used a set or the sum formula — both work! The theory below shows a third way, with XOR, that uses no extra memory and runs no risk of overflow.
The theory: the properties of XOR
XOR compares bit by bit and gives 1 where the bits differ. From this come three properties that, together, are a powerful tool:
1. a ^ a = 0 (anything XOR'd with itself cancels out)
2. a ^ 0 = a (XOR with zero changes nothing)
3. a ^ b = b ^ a (order doesn't matter — commutative and associative)
Put it all together: if you XOR a bunch of numbers, everything that appears in a pair cancels out (property 1) and what's left is exactly what appeared an odd number of times. It's an "unpaired detector" that stores nothing in memory.
The signs of XOR in the statement
- "Every element appears twice, except one" → the loner is left over.
- "A number is missing" from a known sequence → pair up what exists with what should exist; the missing one is left over.
- "Swap two values without an auxiliary variable", "find the bit difference".
- An O(1) space constraint on a problem that would seem to call for a hash set.
Example 1 — Missing Number
"An array has n distinct numbers from 0..n; one is missing."
- Brute force / hash: mark the present ones in a set and see which is missing — O(n) time but O(n) space.
- Sum:
sum(0..n) − sum(nums)gives the missing one — O(1) space, but the sum can overflow for huge integers. - XOR (no overflow, no memory): XOR all the indices
0..nwith all the values. Each present number appears as an index and as a value → it cancels. The only index with no matching value is the missing one — and it's left over.
Watch the accumulator res in binary while the pairs cancel out:
Why is it O(n) time and O(1) space?
A single pass over the n elements, with one XOR (O(1)) per step →
O(n) time. The state is a single accumulator variable, regardless of the
size of the input → O(1) space. And, unlike the sum, the XOR never "grows"
beyond the width of the integer — no risk of overflow.
| Solution | Time | Space | Note |
|---|---|---|---|
| Hash set | O(n) | O(n) | extra memory |
| Gauss sum | O(n) | O(1) | can overflow integers |
| XOR | O(n) | O(1) | no overflow, no memory |
Example 2 — Single Number
"Every element appears twice, except one. Find the loner." It's XOR in its purest form — without even needing the indices:
Start from 0 (property 2: it doesn't get in the way), XOR everything: each
pair vanishes, the loner stays. One line, O(n)/O(1). Try solving this with any
other approach in O(1) space — you'll understand why XOR is special.
🧠 Review quiz
0/41. What is the value of a ^ a, for any a?
2. Why does XOR'ing all the elements of an array where everything appears in pairs (except one) reveal the loner?
3. What advantage does XOR have over the 'Gauss sum' in Missing Number?
4. 'Swap the values of two variables a and b without using an auxiliary variable.' Which tool from this lesson solves it?
Summary
- XOR:
a^a=0,a^0=a, commutative. Pairs cancel out; the unpaired one remains. - Single Number: XOR everything starting from 0 → the loner. O(n)/O(1).
- Missing Number: XOR the indices
0..nwith the values → the missing one is left over, with no overflow and no memory. - Signs: "appears twice except one", "is missing", O(1) space.
Next lesson: techniques that combine bits with other ideas — counting bits,
reverse bits and summing without +.