Lesson 8 — The XOR trick

~20 minutes · Day 5 · XOR cancellation · Python

Tonight's problem is Missing Number. Interviewers like it because the input looks almost too simple: numbers from 0 to n, one missing. The trick is noticing that every number which appears twice can cancel itself away.

The invariant

x XOR x = 0, so XOR-ing 0..n against the array cancels every present number and leaves the missing one.

Python writes bitwise XOR with ^ (Python docs: binary bitwise operations). The only facts you need are small: x ^ x becomes 0, x ^ 0 stays x, and the order does not matter for XOR (Wikipedia: exclusive or).

Missing Number: the slow way first

The problem: given n distinct numbers taken from the range 0..n, return the one number that is missing. A direct brute force is to test every possible number:

def missing_number(nums):
    for want in range(len(nums) + 1):
        if want not in nums:        # scans the list each time
            return want

This is correct, but it is O(n²): there are O(n) possible answers, and want not in nums may scan O(n) items each time. The repeated scan is the cost to remove.

Missing Number: the XOR way

Instead of searching, mix together every number that should exist and every number that does exist. Every present number appears twice in that mix, so it cancels. The missing number appears once, so it survives.

The full range and the array form pairs under XOR; the unpaired value is the missing number.

def missing_number(nums):
    ans = len(nums)                 # include n from the range 0..n
    for i, x in enumerate(nums):
        ans ^= i                    # include range value i
        ans ^= x                    # include array value x
    return ans                      # only the missing value remains

For nums = [3, 0, 1], the loop computes 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1. The two 3s cancel, the two 0s cancel, the two 1s cancel, and 2 is left.

Transfer: paired cards, one loner

Imagine a bag of number cards where every value appears exactly twice except one value, which appears once. Before opening the reveal, say the approach out loud: what should the accumulator start as, and what should each step XOR into it?

def lonely_card(cards):
    ans = 0
    for x in cards:
        ans ^= x                    # pairs cancel: x ^ x = 0
    return ans

What the trick buys you

Missing Number also has a sum formula. Learn the XOR version anyway: it teaches the cancellation move that appears in other disguise problems.

Practice — answer before you scroll past

ans = 0
for i, x in enumerate(nums):
    ans ^= i
    ans ^= x
return ans

Your move (tonight)

Solve Missing Number in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Predict: state the brute force and the XOR invariant before coding.
2. Attempt: write the one-pass XOR version from memory.
3. Compare: watch the source below only after your attempt.
4. Encode: save the invariant in your own words for revision day.