The problem
Every number in the list appears twice except one. Find that single number using constant extra space.
Input: [4, 1, 2, 1, 2] Output: 4
Picture it
Picture socks: every sock has a twin except one. XOR (^) works like a light switch: flipping it twice puts it back. If we XOR all the numbers together, every pair switches its lights on and then off again, leaving only the lonely sock’s lights on.
How to recognise it
- Every value appears exactly twice except one, and you must find the odd one out.
- The problem asks for O(1) extra space, which rules out a dictionary or set of counts.
- "Pairs cancel" is the hint for XOR (
^, exclusive or):x ^ x == 0,x ^ 0 == x, and the order of the operations does not matter. - Up to 3 × 10^4 numbers, between −3 × 10^4 and 3 × 10^4.
Start with brute force
For each number, count how often it appears; return the one that appears once.
def single_brute(nums):
for x in nums:
if nums.count(x) == 1:
return x
Each count scans the whole list, so this is O(n²) time and O(1) space. With n = 3 × 10^4 that can reach about 9 × 10^8 comparisons, far too slow in Python. A dictionary of counts fixes the time (O(n)) but uses O(n) extra space, which the problem forbids.
From brute force to the idea
- Find the waste. We do not need the counts themselves, only whether each count is odd or even.
- Think of each bit as a switch. XOR with a number flips the switches where that number has a 1 bit. Flipping a switch twice puts it back.
- Fold everything together. Start with
acc = 0and XOR in every number. Because XOR is commutative and associative, the result is the same as if equal numbers were next to each other: each pair gives 0, and 0 changes nothing. - What remains is the single. After all pairs cancel,
accholds exactly the number that appeared once.
This is the key idea: XOR of all the numbers cancels every pair and leaves the single one, using one variable.
For example, 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.
The key idea
a ^ a = 0 and a ^ 0 = a, so XOR of everything is the single number. O(n), O(1).
Python solution
def single_number(nums):
acc = 0
for x in nums:
acc ^= x # a pair flips a switch twice: back off
return accIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (count each) | O(n²): a full scan per number | O(1) |
| Dictionary of counts | O(n): one pass | O(n): one entry per distinct value |
| XOR fold (shown code) | O(n): one XOR per number | O(1): a single accumulator |
Edge cases
- One number only (
[7]): returns 7. - The single number is 0 (
[0, 4, 4]): returns 0, correctly. - Negative numbers (
[-1, -1, 5]or[2, 2, -3]): work, because Python's XOR on negative integers behaves like two's complement with unlimited width; pairs still cancel. - The promise is broken (some value appears three times): the answer is wrong.
[1, 1, 1, 3, 3, 7]returns 6 (1 ^ 7), not 7. XOR only tracks odd versus even counts. - Empty list: returns 0, which is not a real answer; LeetCode guarantees at least one number.
Common mistakes
- Starting
accat the first number and then XOR-ing the whole list again, which cancels that number. - Using
+and-to cancel pairs: you cannot know whether to add or subtract a value without remembering it. - Sorting first to compare neighbours: correct, but O(n log n) and it changes or copies the list.
- Expecting XOR to work when values appear three times each.
Now every number appears twice except two different ones (LeetCode 260). Return both, in any order. For [1, 2, 1, 3, 2, 5] the answer is 3 and 5. Use O(1) extra space. Describe your approach, then write it if you like.
Compare with our answer
XOR of everything gives x ^ y, the two singles combined. It is not 0 (they differ), so pick any 1 bit in it: xy & -xy keeps the lowest one. That bit is 1 in one single and 0 in the other, so it splits all numbers into two groups, each with one single and only whole pairs. XOR each group.
def single_two(nums):
xy = 0
for x in nums:
xy ^= x # x ^ y, the two singles
low = xy & -xy # a bit where x and y differ
a = 0
for x in nums:
if x & low:
a ^= x
return [a, xy ^ a]
Time O(n), space O(1). It works for negative numbers in Python too.
A strong answer mentions: why x ^ y is not zero, choosing a bit where they differ, and that pairs always land in the same group.
1. A log lists every opened file once and every closed file once; exactly one file is still open. Each file opens at most once. Which approach fits best?
Each closed file appears twice, so its id cancels, and the single open file's id remains in O(n) time and O(1) space. Sorting costs O(n log n), and a set needs O(n) memory.
2. Why does the order of the numbers not matter to the XOR fold?
Like addition, a ^ b == b ^ a and (a ^ b) ^ c == a ^ (b ^ c), so the list can be regrouped into pairs that cancel. No sorting or resetting happens.
3. For which input does the shown code return a wrong answer?
Three 1s leave one 1 behind, so the result is 1 ^ 7 = 6 instead of 7. The other inputs keep the promise (pairs and one single), and XOR handles 0 and negatives correctly.
Score 60% or more and the lesson is marked complete.