Single Number
Find the one value that appears once when every other appears twice — and see why XOR removes the need for any memory at all
Problem Statement
Every element in the array appears twice, except for one which appears once. Find that one.
You must solve it in O(n) time and O(1) extra space.
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Input: nums = [2, 2, 1]
Output: 1
Input: nums = [1]
Output: 1Intuition
The obvious solution is a hash map: count everything, then look for the count of 1.
[4, 1, 2, 1, 2] → {4: 1, 1: 2, 2: 2} → answer 4That is O(n) time, which is fine — but O(n) memory, which the problem forbids. So the question is really: how do you remember what you have seen without storing it?
A sum will not work: 4 + 1 + 2 + 1 + 2 is 10, and 10 tells you nothing. You need an operation where a value meeting its twin destroys both.
The insight
XOR is exactly that operation.
x ^ x = 0 a value cancels itself
x ^ 0 = x cancelling with nothing changes nothing
a ^ b = b ^ a order does not matterXOR the whole array together. Every pair annihilates itself, whatever order the pairs appear in. Whatever is left over must be the unpaired value.
The third rule is what makes this work on an unsorted array. The two 1s are not next to each other, and they do not need to be — XOR does not care when they arrive.
Approach
Start with 0
0 is the identity for XOR — combining with it changes nothing. It is the correct empty starting point, the same way 0 is for a sum.
XOR every element into a running total
One variable. One pass. No condition, no comparison, no lookup.
The total is the answer
Every paired value has cancelled to 0, leaving 0 ^ single, which is single.
Following it in bits
4 = 1 0 0
^ 1 = 0 0 1
-------
1 0 1 (5)
^ 2 = 0 1 0
-------
1 1 1 (7)
^ 1 = 0 0 1
-------
1 1 0 (6)
^ 2 = 0 1 0
-------
1 0 0 (4) ← the bits of 4, untouchedLook at the rightmost column: it flips to 1 when the first 1 arrives and back to 0 when the second does. Each column is running its own independent cancellation.
Solution
def single_number(nums: list[int]) -> int:
"""Return the only value appearing once; all others appear twice.
XOR cancels equal values, so the paired ones vanish and the
unpaired one survives. O(n) time, O(1) space.
"""
result = 0
for num in nums:
result ^= num
return resultThe whole loop is one line, and it can be written as functools.reduce(operator.xor, nums, 0) — but the explicit loop is clearer about what is happening.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time — one pass, one XOR per element. XOR is a single machine instruction, so the constant factor is as small as it gets.
Space — one integer, regardless of input size. This is the requirement the hash map version fails, and the reason the problem exists.
Edge Cases
Related Problems
- Missing Number — the same cancellation, but you supply the missing partner yourself
- Contains Duplicate — the hash-set approach this problem forbids
- Number of 1 Bits — the other essential bit operation