Math & Bit Manipulation · LC #136
Single Number
Every element in the array appears exactly twice except one - find that single element in O(n) time and O(1) space using XOR.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a non-empty array of integers where every element appears twice except for one, find that single one. Must run in O(n) time and O(1) space.
Sample I/O
Input: nums = [2,2,1] Output: 1 Input: nums = [4,1,2,1,2] Output: 4
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
XOR has two key properties: `a ^ a = 0` (any number XORed with itself cancels) and `a ^ 0 = a` (any number XORed with 0 is unchanged). XORing all elements together causes all pairs to cancel, leaving only the unpaired number.
Core Concept
Fold the entire array with XOR: `result = nums[0] ^ nums[1] ^ ... ^ nums[n-1]`. All duplicate pairs evaluate to 0; the single number XORed with 0 is itself. XOR is commutative and associative, so order does not matter.
When to use
Exactly-one-odd-occurrence problems; finding the differing bit between two values; detecting bit flips in hardware checksums.
When NOT to use
When elements appear an odd number > 1 times (use bit counting per-position instead). When you need the index of the single element rather than its value - XOR does not track positions.
Key Insights
What to Know Cold
- XOR is its own inverse: `a ^ a = 0` - pairs self-destruct.
- Commutativity + associativity guarantee order independence.
- This is O(1) space - no hash map, no sorting, no auxiliary array.
- The same XOR trick generalises: if one element appears once and all others appear 3 times, use 32-bit per-position counting modulo 3.
- Python's `functools.reduce` and TypeScript's `Array.reduce` express this as a one-liner fold.
1 example
Worked Examples
XOR cancellation trace
nums = [4,1,2,1,2]
XOR all: 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4
singleNumber([4,1,2,1,2]); // 0^4=4, 4^1=5, 5^2=7, 7^1=6, 6^2=4 → 4
Shows XOR self-cancellation in O(1) space with no sorting or hashing.