4.30.1 — Single Number

LeetCode 136 · Easy · ★ Blind 75

The problem

Every element appears twice except one, which appears once. Find it. You must use O(n) time and O(1) space.

[2,2,1]        →  1
[4,1,2,1,2]    →  4

The pattern

The O(1) space requirement rules out a hash set, a counter and sorting-with-a-copy. What is left is arithmetic on the values themselves.

XOR every element together.

Three properties do all the work:

x \oplus x = 0 \qquad x \oplus 0 = x \qquad \text{order does not matter}

So every pair cancels to 0, leaving 0 ^ single = single. The order is irrelevant, which means one pass with no bookkeeping.

The solution

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for n in nums:
            result ^= n
        return result

TypeScript

function singleNumber(nums: number[]): number {
  let result = 0;
  for (const n of nums) result ^= n;
  return result;
}

Python has a one-liner worth knowing:

from functools import reduce
from operator import xor
return reduce(xor, nums)

Starting at 0 is what makes it work, since 0 ^ x = x. It is the identity element for XOR, exactly as 0 is for addition.

Trace

[4,1,2,1,2]

4 ^ 1 ^ 2 ^ 1 ^ 2. Reorder freely: 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4 ✓.

The reordering is legal because XOR is commutative and associative — and that is precisely why the array's order does not matter.

Complexity

O(n) time, O(1) space.

Why not sum-based arithmetic?

A tempting alternative: 2 × sum(set(nums)) − sum(nums). It works, and it needs O(n) space for the set — so it fails the constraint. It can also overflow on large values, while XOR never can.

XOR never overflows, because it is bitwise and never produces a bit that was not already in range. That is a genuine advantage worth mentioning.

The variants, and where they get interesting

Single Number II (LeetCode 137) — every element appears three times except one. XOR no longer cancels, because three copies leave one behind.

The fix generalises the idea: count the set bits at each position across all numbers, then take each count modulo 3. A bit belonging to the tripled numbers appears a multiple of three times; a bit of the single number leaves a remainder.

result = 0
for bit in range(32):
    count = sum((n >> bit) & 1 for n in nums)
    if count % 3:
        result |= (1 << bit)

O(32n) time and O(1) space. There is a clever two-variable version using ones and twos, but the bit-counting version is the one you can derive under pressure and explain.

Single Number III (LeetCode 260) — two numbers appear once, the rest twice.

XOR everything and you get a ^ b, the two answers combined. Now use x & -x to isolate any bit where they differ — that bit is 1 in one answer and 0 in the other. Partition the array by that bit and XOR each half separately.

xor_all = 0
for n in nums: xor_all ^= n
lowest = xor_all & -xor_all          # a bit where a and b differ
a = b = 0
for n in nums:
    if n & lowest: a ^= n
    else: b ^= n
return [a, b]

That partition-by-a-differing-bit move is the transferable idea, and it is why x & -x is worth having in your fingers.

Where this goes next

• Missing Number — XOR the indices with the values. 4.30.5.
• Find the Duplicate Number — when mutation and extra space are both banned, XOR does not help and it becomes cycle detection. 4.9.8. Knowing when XOR does not apply is as useful as knowing when it does.
• Checksums and parity bits — a parity bit is the XOR of a message's bits, and it detects any single-bit flip. Chapter 1.8 covers error detection properly.
• RAID 5 — the parity disk stores the XOR of the others, so any one failed disk can be reconstructed. The same cancellation, at hardware scale.

What the interviewer will push on

"Why does XOR work?" The three properties. Say all three; the commutativity is what makes order irrelevant.

"Why start at 0?" It is XOR's identity.

"What if every element appeared three times?" Count bits modulo 3.

"What if two numbers appeared once?" XOR everything, isolate a differing bit with x & -x, partition, XOR each half.

"Why not sum-based arithmetic?" It needs a set, and it can overflow.

One thing to volunteer: mention RAID parity. It shows the cancellation property is a real engineering tool, not a puzzle trick.

Next: 4.30.2 Number of 1 Bits — counting set bits, and the idiom that makes it fast.