XOR Cancellation: How Pairs Disappear Like Magic

Most people first encounter XOR in a LeetCode problem and think "wait, what just happened?" The solution is three lines of code, but it feels like a magic trick. Numbers go in, pairs vanish, and the lone survivor pops out.

It is not magic. It is a bitwise operation with a very specific property, and once you understand that property, the "trick" becomes obvious. Let's build that understanding from scratch.

What is XOR?

XOR stands for "exclusive or." It is a bitwise operation, meaning it works on individual bits (the 0s and 1s that make up every number in a computer).

Here is the rule: XOR outputs 1 when the two input bits are different, and 0 when they are the same.

That is the entire definition. "Are these two bits different?" If yes, the result is 1. If no, the result is 0.

In Python, the XOR operator is ^. When you write 5 ^ 3, Python compares each pair of bits:

  5 in binary:  1 0 1
  3 in binary:  0 1 1
                -----
  5 ^ 3:        1 1 0  =  6

Bit by bit: 1 vs 0 is different, so 1. 0 vs 1 is different, so 1. 1 vs 1 is the same, so 0. Result: 110 in binary, which is 6.

That is all XOR does. Compare bits, output 1 for differences.

The three properties that matter

XOR has three properties that make it incredibly useful for algorithm problems. These are not arbitrary rules you need to memorize. They all follow directly from the "same = 0, different = 1" definition.

Property 1: x ^ x = 0

XOR a number with itself, and every bit cancels out. Think about it: for each bit position, the two inputs are identical, so XOR produces 0.

  4 in binary:  1 0 0
  4 in binary:  1 0 0
                -----
  4 ^ 4:        0 0 0  =  0

Every bit matches, so every output bit is 0. This works for any number. 1 ^ 1 = 0. 999 ^ 999 = 0. 2147483647 ^ 2147483647 = 0. Always.

Property 2: x ^ 0 = x

XOR a number with 0, and you get the original number back. Zero has all bits set to 0, so every bit in x is compared against 0. If the bit was 1, it is "different" from 0, so the result is 1. If the bit was 0, it is "same" as 0, so the result is 0. The original number survives unchanged.

  4 in binary:  1 0 0
  0 in binary:  0 0 0
                -----
  4 ^ 0:        1 0 0  =  4

Property 3: XOR is commutative and associative

The order does not matter. a ^ b = b ^ a (commutative). And (a ^ b) ^ c = a ^ (b ^ c) (associative). You can rearrange and regroup XOR operations however you want without changing the result.

This is just like addition: 2 + 3 = 3 + 2, and (2 + 3) + 4 = 2 + (3 + 4). XOR follows the same rules.

Why pairs cancel: a binary walkthrough

Let's see this in action with actual bits. Take the array [4, 1, 2, 1, 2]. Every number except 4 appears twice.

If we XOR all of them together, the order does not matter (Property 3). So let's group the pairs:

4 ^ 1 ^ 2 ^ 1 ^ 2

Rearrange (commutative + associative):

(1 ^ 1) ^ (2 ^ 2) ^ 4

Apply Property 1 (x ^ x = 0):

0 ^ 0 ^ 4

Apply Property 2 (x ^ 0 = x):

4

The paired numbers annihilate each other. The lone number is all that remains.

The Single Number problem

LeetCode Single Number (Problem 136) asks exactly this: given a non-empty array of integers where every element appears twice except for one, find that single one.

The constraints say you must use O(1) extra space. That rules out hash maps, sets, and sorting with extra storage. XOR is the tool built for this job.

The code

def single_number(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

That is it. Three lines of logic. Start with 0, XOR every element, and whatever is left is the answer.

You could also write it as a one-liner with reduce:

from functools import reduce
from operator import xor

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums)

Both versions do the same thing. The explicit loop is clearer for interviews.

Step-by-step walkthrough

Let's trace through [4, 1, 2, 1, 2] to watch the cancellation happen in real time.

Notice what happened. When 1 appeared the second time (step 4), the bits from the first 1 got cancelled. When 2 appeared the second time (step 5), those bits cancelled too. Only the bits from 4 survived the entire process.

The key insight is that you do not need to group the pairs next to each other. XOR is commutative and associative, so the cancellation happens automatically no matter what order the elements appear in.

Why this is O(1) space

The "obvious" solution to Single Number is to use a hash map or a set to count occurrences:

# Works, but uses O(n) space
def single_number_hashmap(nums: list[int]) -> int:
    counts: dict[int, int] = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
    for num, count in counts.items():
        if count == 1:
            return num
    return -1  # should never reach here

This is O(n) time and O(n) space. It stores every unique number in a dictionary.

The XOR approach uses a single integer variable. No dictionary. No set. No extra array. Just one int that accumulates the XOR. That is O(1) space, which is what the problem demands.

Complexity analysis

*Sorting is O(1) extra space only if done in-place, but it modifies the input array.

XOR wins on both dimensions: linear time, constant space, and no side effects.

Other problems that use XOR

Once you understand the cancellation property, a whole family of problems opens up.

Missing Number (LeetCode 268)

Given an array of n numbers from 0 to n, one number is missing. Find it.

The trick: XOR all the numbers in the array with all the numbers from 0 to n. Every number that is present appears twice (once in the array, once in the range), so they cancel. The missing number appears only once and survives.

def missing_number(nums: list[int]) -> int:
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

Find Two Non-Repeating Numbers

A harder variant: every element appears twice except for two elements. Find both.

XOR all elements together. The result is a ^ b (the XOR of the two unique numbers). Since a != b, at least one bit in the result is 1. Use that bit to partition the array into two groups, one containing a and one containing b. XOR each group separately to isolate them.

def single_numbers(nums: list[int]) -> list[int]:
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Find a bit where a and b differ
    diff_bit = xor_all & (-xor_all)

    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num
    return [a, b]

Single Number II (LeetCode 137)

Every element appears three times except one. XOR alone is not enough here (triples do not cancel with basic XOR), but the bit-level thinking you develop from XOR cancellation is exactly the foundation you need to solve it.

The building blocks

This problem decomposes into one core reusable piece that CodeBricks drills independently:

XOR cancellation (accumulate XOR across a collection)

The act of initializing a result to 0 and XOR-ing every element into it. This micro-pattern is the backbone of duplicate cancellation, missing element detection, and parity-based reasoning across many problems.

result = 0
for item in collection:
    result ^= item
# result now holds the XOR of all unpaired elements

This building block is deceptively simple. It is just a loop with ^=. But recognizing when to use it is the hard part. Whenever a problem says "every element appears twice except one" or "find the missing element in a range," XOR accumulation should be your first instinct.

The same pattern extends to the two-unique-numbers variant (partition by a differing bit, then XOR each partition) and to detecting errors in data transmission (checksums). Learning it as an isolated building block means you will recognize it instantly in these more complex settings.

Common mistakes

1. Forgetting that x ^ 0 = x. If you initialize your result to something other than 0, you are introducing an extra value into the XOR chain. Always start at 0.

2. Trying to use XOR when elements appear more than twice. XOR cancellation only works when duplicates come in pairs. If an element appears three times, x ^ x ^ x = x (one pair cancels, one copy remains). For non-pair multiplicities, you need different techniques.

3. Thinking XOR only works on small numbers. XOR works on any integer, including negative numbers (which are stored in two's complement). The bit-level cancellation property holds regardless of the number's size or sign.

When to use this pattern in interviews

Look for these signals:

• The problem says "every element appears twice except one"
• You need O(1) space and the input involves pairs
• The problem mentions finding a "missing" element in a known range
• Constraints explicitly rule out extra data structures

If you see "find the single/missing element" combined with "constant space," XOR cancellation is almost certainly the intended solution.

Related posts

• Contains Duplicate - The set-based approach to duplicate detection. XOR cancellation is the O(1)-space alternative when you know the duplicate structure.
• Hash Map Patterns - Hash maps solve many of the same problems XOR does, but with O(n) space. Understanding both lets you choose the right tool.
• Two Pointer Pattern - Another O(1)-space technique worth learning alongside XOR

XOR cancellation is one of those patterns that feels like a magic trick the first time you see it. But once you understand why it works (same bits cancel, different bits survive, and order does not matter), the magic dissolves into simple logic. The real skill is not knowing the trick. It is recognizing when a problem is secretly asking for it.

That recognition comes from practice. You drill the XOR accumulation pattern as an isolated building block, typing it from scratch at increasing intervals. After a few repetitions, you stop thinking about the bit-level mechanics entirely. You just see "pairs cancel" and the code flows out of your fingers.