Single Number
Problem statement
You are given a non-empty list of integers nums. Every value appears exactly twice, except for one value that appears only once. Return that single value.
The challenge: do it in one pass over the list (linear time) using only a fixed amount of extra memory, no matter how long the list is.
Think of request IDs in a log where every request writes a "start" line and an "end" line with the same ID. One request never finished — which ID is it?
Examples
Example 1
Input: nums = [2,2,1]
Output: 1
Explanation: 2 appears twice and 1 appears once, so the answer is 1.
Example 2
Input: nums = [4,1,2,1,2]
Output: 4
Explanation: 1 and 2 each appear twice; 4 is the only value without a partner.
Example 3
Input: nums = [1]
Output: 1
Explanation: A list with a single value has nothing to pair it with, so that value is the answer.
Hints
Approach
Optimal: XOR everything
Intuition
XOR (written ^) compares two numbers bit by bit: a result bit is 1 when the two bits differ and 0 when they are the same. That gives it three useful rules:
x ^ x = 0— a value cancels itself out.x ^ 0 = x— XOR with 0 changes nothing.- The order doesn't matter:
a ^ b ^ ais the same asa ^ a ^ b.
So XOR all the values together. Thanks to the third rule, you can imagine the pairs lined up next to each other; each pair cancels to 0, and what's left is the single value XORed with 0 — the single value itself. One pass, one number of memory.
Steps
- Set
result = 0. - For each value
x, setresult = result ^ x. - Return
result.
Dry run
nums = [4,1,2,1,2] (bits shown in 3-bit binary)
| x | x in binary | result after |
|---|---|---|
| start | 000 (0) | |
| 4 | 100 | 100 (4) |
| 1 | 001 | 101 (5) |
| 2 | 010 | 111 (7) |
| 1 | 001 | 110 (6) |
| 2 | 010 | 100 (4) |
The 1s and 2s cancel out, leaving 4. Edge cases: [1] returns 0 ^ 1 = 1. Negative numbers work too, because XOR works on their bit patterns the same way.
Complexity
Time O(n) - We go through the list once and do one XOR per value. XOR is a single, very fast machine operation. There is no second pass and no map. For 30,000 values that is 30,000 XORs.
Space O(1) - Only one number, the running XOR, is kept. It doesn't grow with the input. This meets both of the problem's limits.
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for x in nums:
result ^= x
return result
if __name__ == "__main__":
print(Solution().singleNumber([2, 2, 1])) # 1
print(Solution().singleNumber([4, 1, 2, 1, 2])) # 4
print(Solution().singleNumber([1])) # 1RecapThe whole problem in a few lines, for the night before
- Spot it: every value appears twice except one; linear time and constant memory required
- Idea: XOR all values — pairs cancel (
x ^ x = 0), leaving the single one - Cost: O(n) time, O(1) space
- Trap: using a hash map or set works but breaks the O(1) memory rule
- Remember: order doesn't matter for XOR, so pairs cancel wherever they are
Interview follow-ups
Every value appears three times except one. How do you find it?
XOR no longer cancels, because
x ^ x ^ x = x. Instead, count how many values have each bit set; for each of the 32 bit positions, the count modulo 3 is the single value's bit. That is O(32·n) = O(n) time and O(1) space. This is LeetCode's Single Number II.Two values appear once and all others twice. Return both.
XOR everything to get
a ^ b, which is not 0 becausea ≠ b. Pick any bit that is 1 in it —aandbdiffer there. Split all values into two groups by that bit and XOR each group separately: the pairs still cancel inside each group, leavingain one andbin the other. Still O(n) time and O(1) space.The values arrive as a stream too large to store. Does the approach still work?
Yes — XOR needs only the running result, so read one value at a time, XOR it in, and never store the stream. Memory stays O(1) however long the stream is. This is why it fits the log-matching use case: you can find the unmatched request ID in a single pass over a huge log.
Frequently asked questions
XOR is commutative (a ^ b = b ^ a) and associative ((a ^ b) ^ c = a ^ (b ^ c)), so you can reorder and regroup the values any way you like without changing the result. That means 4 ^ 1 ^ 2 ^ 1 ^ 2 equals 4 ^ (1 ^ 1) ^ (2 ^ 2), which is 4 ^ 0 ^ 0 = 4. The positions of the pairs never matter.
After sorting, equal values sit next to each other, so you can step through in pairs and return the first value that doesn't match its neighbour. That takes O(n log n) time and O(1) extra space if you sort in place. It is a valid middle ground, but it's slower than XOR and changes the input.
Yes: 2 × sum(distinct values) − sum(all values) equals the single value, because every paired value is counted twice in the first sum. But building the set of distinct values needs O(n) memory, and in Java or C++ big sums can overflow. XOR has neither problem.
Yes. XOR works on the bit patterns of the numbers, and a negative number is just another bit pattern (two's complement). x ^ x is 0 for any x, negative or not, so the pairs still cancel. Python's integers behave the same way with ^.
Finding the one unmatched item among pairs is a real debugging task: a request with a start log line but no end, a lock acquired but never released, or a connection opened but never closed. The XOR trick is also the idea behind simple checksums and parity checks, such as RAID parity that can rebuild one missing disk from the others.
