Single Number: XOR Cancellation in One Pass

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

The constraints are strict. You must run in linear time and use constant extra space. That rules out hash maps, sets, and sorting. The intended tool is XOR.

The XOR cancellation property

XOR is a bitwise operation. It compares two bits and outputs 1 when they differ, 0 when they match. In Python, the operator is ^.

Three properties make XOR perfect for this problem:

When you XOR all elements of an array together, every number that appears twice cancels itself to 0. And XOR-ing with 0 leaves the remaining number untouched. The pairs vanish. The single number survives.

The approach

The algorithm is almost absurdly simple:

1. Initialize result = 0
2. XOR every element into result
3. Return result

Because XOR is commutative and associative, the order of elements does not matter. Pairs will always find each other and cancel to 0, regardless of where they sit in the array.

Python solution

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

Walkthrough: [4, 1, 2, 1, 2]

Let's trace the algorithm on [4, 1, 2, 1, 2]. The answer should be 4, since 1 and 2 each appear twice.

When 1 appeared the second time (step 4), its bits cancelled against the first occurrence. When 2 appeared the second time (step 5), the same thing happened. Only the bits from 4 survived the entire pass.

You do not need to group pairs next to each other. XOR is commutative and associative, so the cancellation happens automatically regardless of element order.

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 and constant space with no side effects.

The building blocks

This problem decomposes into one reusable building block that CodeBricks drills independently:

XOR cancellation (accumulate XOR across a collection)

Initialize a result to 0 and XOR every element into it. Pairs cancel to 0, and only unpaired values survive. 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

The pattern is deceptively simple. It is just a loop with ^=. But recognizing when to reach for it is the real skill. 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.

Edge cases

Single element array. If nums has only one element, the loop XORs that element with 0 and returns it immediately. 0 ^ x = x, so the answer is correct.

Large arrays. XOR is a constant-time bitwise operation. Whether the array has 10 elements or 10 million, each step takes the same amount of work. The algorithm stays O(n) regardless of scale.

Negative numbers. XOR works on the binary representation of integers, including negative numbers stored in two's complement. (-3) ^ (-3) = 0 just like 3 ^ 3 = 0. The cancellation property holds for any integer value.

From understanding to recall

Reading through the XOR cancellation property is the first step. But in an interview, you need the pattern to fire instantly when you see the right signals. That recall gap is where most people get stuck.

The fix is deliberate 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 bit-level mechanics. You see "pairs cancel" and the code flows out of your fingers.

That is the difference between understanding a solution and owning it.

Related posts

• XOR Cancellation Pattern - A deep dive into XOR from the ground up, including the truth table, all three properties, and extended variants like finding two non-repeating numbers.
• Number of 1 Bits - Another bit manipulation problem. Uses n & (n - 1) to clear the lowest set bit, a different but complementary technique to XOR.