XOR Tricks Explained: Single Number, Missing Number, Two Singles

"Every number appears twice except one. Find it in linear time and constant memory." The answer is a single loop with ^= in it, and it looks like a party trick until you see the three algebraic facts underneath. Once those are clear, the same loop solves a family of problems — and you can see exactly where it stops working.

The problem it solves

The classic version: an array where every value appears exactly twice except one, which appears once. Return the lonely value.

A hash set or a counter solves it in O(n) time but O(n) memory. Sorting solves it in O(1) extra memory but O(n log n) time. XOR gets both bounds at once: one pass, one integer of state.

Its relatives use the same idea:

• Missing number: the array holds 0 to n with exactly one value absent.
• Two singles: every value appears twice except two, which appear once each.

The intuition

XOR compares two numbers bit by bit and outputs 1 where the bits differ. Three facts follow directly from that definition:

1. x ^ 0 == x — XOR with zero changes nothing.
2. x ^ x == 0 — a number differs from itself nowhere.
3. XOR is commutative and associative — order and grouping do not matter.

Now fold an entire list into one accumulator starting at 0. Because order does not matter, you may as well imagine the list rearranged so equal values sit next to each other. Each pair cancels to 0 by fact 2, and the lone survivor passes through the zeros by fact 1. The accumulator ends at the single number.

Think of each bit position as a light switch. Every occurrence of a value flips the switches where it has 1s. A value seen twice flips its switches twice and leaves them as they were. Only the single value's switches end up changed.

Missing number becomes the same problem with a second list. XOR together every index 0 to n and every value in the array. Each present value meets its own index and cancels; the absent one has no partner.

Two singles needs one extra step. Folding the whole list leaves a ^ b, not a and b. But since a != b, that result has at least one 1 bit, and at that position a and b differ. Split the list into two groups by that bit. a and b land in different groups, and every pair lands together in one group, because equal numbers have equal bits. Fold each group and each yields one single.

Watch it run

The accumulator starts at zero and folds in [4, 1, 2, 1, 2], with the incoming value drawn in bit lanes above it. Watch each first occurrence switch a lane on, the second 1 switch the same lane straight back off, and the 2 cancel the same way even though it was not adjacent to its partner. The value left standing is 4.

The code

All three problems, plus the bit trick that isolates the lowest set bit:

from functools import reduce
from operator import xor

def single_number(nums):                # every value twice except one
    acc = 0
    for x in nums:
        acc ^= x                        # pairs cancel: x ^ x == 0
    return acc

def missing_number(nums):               # 0..n with one value absent
    acc = len(nums)
    for i, x in enumerate(nums):
        acc ^= i ^ x                    # every present value meets its index
    return acc

def two_singles(nums):                  # every value twice except TWO
    both = reduce(xor, nums, 0)         # = a ^ b, nonzero because a != b
    low = both & -both                  # one bit where a and b differ
    a = 0
    for x in nums:
        if x & low:                     # split on that bit: a and b land apart
            a ^= x
    return sorted((a, both ^ a))

print(single_number([4, 1, 2, 1, 2]))           # 4
print(missing_number([3, 0, 1]))                # 2
print(two_singles([1, 2, 1, 3, 2, 5]))          # [3, 5]
print(6 & -6, bin(6), bin(6 & -6))              # 2 0b110 0b10

both & -both keeps only the lowest 1 bit. In two's complement, -x is ~x + 1: inverting flips every bit, and adding one carries through the trailing 1s back to the first position where x had a 1. Only that bit is set in both. Python integers behave as if they had infinitely many sign bits, so this works for negative inputs too.

Each function is checked against a Counter — count every value, report the ones seen once — on random arrays that include negatives and shuffled pairs. The last lines show the XOR swap and the case where it breaks:

import random
from collections import Counter

def xor_swap(a, i, j):
    a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j]

random.seed(5)
ok = True
for _ in range(3000):
    pool = random.sample(range(-50, 50), random.randint(3, 12))
    singles, pairs = pool[:2], pool[2:]
    one = pairs + pairs + [singles[0]]
    random.shuffle(one)
    two = pairs + pairs + singles
    random.shuffle(two)
    counts = Counter(one)               # brute force: count and look
    ok &= single_number(one) == [x for x in counts if counts[x] == 1][0]
    counts = Counter(two)
    ok &= two_singles(two) == sorted(x for x in counts if counts[x] == 1)
    n = random.randint(1, 30)
    gone = random.randint(0, n)
    rest = [x for x in range(n + 1) if x != gone]
    random.shuffle(rest)
    ok &= missing_number(rest) == (set(range(n + 1)) - set(rest)).pop()
print(ok)                               # True

cells = [7, 9]
xor_swap(cells, 0, 1); print(cells)     # [9, 7]
xor_swap(cells, 0, 0); print(cells)     # [0, 7]  -- same slot: the value is wiped

The complexity

Every function is one or two linear passes with a fixed number of integer variables: O(n) time and O(1) extra memory. That constant memory is the whole reason to use XOR; if memory is not a constraint, a counter is clearer and handles more cases.

Where it goes wrong

• Values that appear three times. Three flips leave a switch on, so the cancellation argument collapses. "Every value three times except one" needs per-bit counting modulo 3, not a plain fold.
• Two singles with one fold. Folding gives a ^ b. Without the split on a differing bit you cannot separate them.
• XOR swap on the same slot. When i == j, the first line computes x ^ x and writes 0 into the only copy. The output above shows 7 becoming 0. Tuple assignment is clearer and has no such case.
• Missing number without the n. The indices run from 0 to n - 1, but the values run to n. Starting the accumulator at len(nums) supplies the missing top index.

For the bit operations themselves — AND, OR and XOR lane by lane — see binary and bitwise ops.

How to say it in an interview

"XOR of a number with itself is zero, XOR with zero is the identity, and XOR is commutative and associative. So if I XOR every element, each pair cancels regardless of position and the single value is what's left. One pass, one variable: O(n) time, O(1) space."

If the follow-up is "two singles", say the plan before coding: fold everything to get a ^ b, take its lowest set bit, and use that bit to split the array so the two singles are in different halves. Being able to state why the pairs never get split is what the question is really testing.