XOR earns its own page because it has one property no other operator has, and that property solves a whole family of problems:

$x \oplus x = 0$ and $x \oplus 0 = x$.

So XOR-ing a collection cancels everything that appears an even number of times and leaves exactly what appears an odd number of times — without a hash map, in $O(1)$ space, and in any order, because XOR is commutative and associative.

Once you see XOR as a self-cancelling accumulator, “find the element that appears once among pairs” stops being a puzzle and becomes a one-liner.

What you’ll learn

• The four identities that make XOR work, and the $O(1)$-space single-number trick.
• The lowest set bit idiom x & -xx & -x, and how it splits a problem in two.
• Why “appears three times” needs a different technique entirely.
• The bitwise trie: how “prefix” can mean bit prefix, turning maximum-XOR from $O(n^2)$ into $O(32n)$.
• Three real LeetCode problems solved in the browser: 136, 260, 421.

The cue

The four identities

Together they mean you can fold a whole array with XOR and the pairs vanish:

def single_number(nums):
    result = 0                    # 0 is the identity
    for n in nums:
        result ^= n               # pairs cancel to 0
    return result
 
 
print(single_number([4, 1, 2, 1, 2]))   # 4

def single_number(nums):
    result = 0                    # 0 is the identity
    for n in nums:
        result ^= n               # pairs cancel to 0
    return result
 
 
print(single_number([4, 1, 2, 1, 2]))   # 4

$O(n)$ time, $O(1)$ space — which is the entire point. A CounterCounter also solves it in $O(n)$ but needs $O(n)$ space, and LC 136 explicitly asks for constant.

The lowest set bit, and splitting in two

LC 260 has two singles. XOR-ing everything gives a ^ ba ^ b — the two answers mixed together, and you cannot separate them from that alone.

But a ^ ba ^ b is non-zero, so it has at least one set bit. Any set bit is a position where aa and bb differ. Pick one, partition the array by that bit, and each half now contains exactly one single — so apply LC 136 twice.

def single_number_iii(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # == a ^ b
 
    bit = xor_all & -xor_all      # isolate the LOWEST set bit
 
    a = b = 0
    for n in nums:
        if n & bit:
            a ^= n                # group where the bit is set
        else:
            b ^= n                # group where it is not
    return [a, b]

def single_number_iii(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # == a ^ b
 
    bit = xor_all & -xor_all      # isolate the LOWEST set bit
 
    a = b = 0
    for n in nums:
        if n & bit:
            a ^= n                # group where the bit is set
        else:
            b ^= n                # group where it is not
    return [a, b]

Bit prefixes and the bitwise trie

LC 421 asks for the maximum XOR over all pairs. Brute force is $O(n^2)$, too slow at $n = 2 \times 10^5$.

Two approaches, both built on the same idea — treat the numbers’ binary representations as strings and reason about prefixes:

def find_maximum_xor(nums):
    best = 0
    for shift in range(31, -1, -1):          # decide the answer bit by bit
        best <<= 1
        prefixes = {n >> shift for n in nums}   # all high-bit prefixes
        candidate = best | 1                    # can we achieve a 1 here?
        if any(candidate ^ p in prefixes for p in prefixes):
            best = candidate
        # else the bit stays 0 (best already has a trailing 0 from the shift)
    return best

def find_maximum_xor(nums):
    best = 0
    for shift in range(31, -1, -1):          # decide the answer bit by bit
        best <<= 1
        prefixes = {n >> shift for n in nums}   # all high-bit prefixes
        candidate = best | 1                    # can we achieve a 1 here?
        if any(candidate ^ p in prefixes for p in prefixes):
            best = candidate
        # else the bit stays 0 (best already has a trailing 0 from the shift)
    return best

The reasoning is greedy from the top: higher bits dominate, so if a 11 is achievable at this position you always take it. And a ^ b = candidatea ^ b = candidate implies candidate ^ a = bcandidate ^ a = b, so checking whether some pair achieves candidatecandidate is a set membership test.

$O(32n)$ time, $O(n)$ space.

The trie version inserts every number as a 32-step path of 00/11 children, then for each number walks down greedily taking the opposite bit wherever that child exists. Same complexity, and it generalises better to problems with extra constraints (LC 1707 adds a limit on which numbers may be used).

The variant map

Practice — real LeetCode problems

LC 136 — Single Number · Easy

Problem. Every element appears twice except for one. Find that one. Your solution must have linear time complexity and use constant extra space.

Constraints. 1 <= len(nums) <= 3 * 10^41 <= len(nums) <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4, and exactly one element appears once.

Examples. [2,2,1][2,2,1] gives 11 · [4,1,2,1,2][4,1,2,1,2] gives 44 · [1][1] gives 11

LC 260 — Single Number III · Medium

Problem. Exactly two elements appear once; every other element appears twice. Return the two singles in any order. Linear time, constant extra space.

Constraints. 2 <= len(nums) <= 3 * 10^42 <= len(nums) <= 3 * 10^4, and the answer is unique.

Examples. [1,2,1,3,2,5][1,2,1,3,2,5] gives [3,5][3,5] (or [5,3][5,3]) · [-1,0][-1,0] gives [-1,0][-1,0] · [0,1][0,1] gives [0,1][0,1]

LC 421 — Maximum XOR of Two Numbers in an Array · Medium

Problem. Return the maximum result of nums[i] ^ nums[j]nums[i] ^ nums[j] over all pairs.

Constraints. 1 <= len(nums) <= 2 * 10^51 <= len(nums) <= 2 * 10^5, 0 <= nums[i] <= 2^31 - 10 <= nums[i] <= 2^31 - 1.

Examples. [3,10,5,25,2,8][3,10,5,25,2,8] gives 2828 (5 ^ 255 ^ 25) · [14,70,53,83,49,91,36,80,92,51,66,70][14,70,53,83,49,91,36,80,92,51,66,70] gives 127127 · [0][0] gives 00

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Single element — [1][1] for LC 136; [0][0] for LC 421.
• Negative numbers — [-1,-1,5][-1,-1,5] and [-1,0][-1,0]; two’s complement makes the identities hold, but test them.
• Zeros in the data — harmless for XOR, since 00 is the identity; [0,1,0][0,1,0] gives 11.
• The two singles differing only in the lowest bit (LC 260) — e.g. [0,1][0,1]; x & -xx & -x still isolates a valid split bit.
• All elements identical in pairs — the accumulator ends at 00, which is only correct if a 00 really is the single.
• Large values near $2^{31}$ (LC 421) — the loop must cover bit 31.
• i == ji == j permitted (LC 421) — so a one-element array returns 00.
• Assuming XOR handles triples — the classic wrong reflex; it does not.

Recap

• XOR is a self-cancelling accumulator: $x \oplus x = 0$, $x \oplus 0 = x$, and it is commutative and associative. Folding an array leaves exactly what appears an odd number of times, in $O(1)$ space.
• For two singles, XOR everything to get a ^ ba ^ b, isolate any set bit with x & -xx & -x, and partition — pairs stay together and cancel, while aa and bb separate. Then it is LC 136 twice.
• x & -xx & -x isolates the lowest set bit through two’s complement; it also drives Fenwick trees.
• XOR’s power comes from pairs. For triples, count set bits mod 3 instead.
• Prefer XOR over sum formulas when overflow is a concern.
• “Prefix” can mean bit prefix: greedy top-down bit construction or a bitwise trie turns maximum-XOR from $O(n^2)$ into $O(32n)$.
• Because XOR is its own inverse, prefix XOR behaves like prefix sums, and the prefix-plus-hash-map pattern transfers directly.

Next: Number Theory for Competitive Programming — primes, modular arithmetic, and the identities worth having memorised.