Given a non-empty array of integers nums, every element appears twice except for one element, which appears once. Find and return that single element.
Your solution must run in linear time and use only constant extra space.
x ^ x = 0, so all the pairs disappear.0 is XOR's identity: x ^ 0 = x. So folding every value into 0 leaves exactly the elements that didn't cancel — here, the single unpaired one.a ^= b; b ^= a; a ^= b.Input: nums = [2, 2, 1] Output: 1 2 appears twice and cancels itself; 1 is the only unpaired value.
Input: nums = [4, 1, 2, 1, 2] Output: 4 1 and 2 each appear twice and cancel; 4 is left alone.
Input: nums = [1] Output: 1 A single element is, trivially, the unpaired one.
- 1 <= nums.length <= 3 * 10^4 - -3 * 10^4 <= nums[i] <= 3 * 10^4 - Every element appears exactly twice except for one element which appears once.
Every number here comes in a matched pair — except one lonely value. You could keep a ledger of everything you've seen, but the elegant answer uses no extra memory at all: it lets a single bitwise operation dissolve the pairs and leave the loner behind.
a ^ b produces a 1 in every position where a and b differ. Everything here rests on it.Naming these up front shows you're pinning down the guarantees before you lean on them.
“Is exactly one element unpaired, always?”
Yes — every other value appears exactly twice, and there's always precisely one loner, so the answer is well-defined.
“Can the array be empty?”
No, it's non-empty; the smallest input is a single element, which is itself the answer.
“Can values be negative?”
Yes. That's fine — XOR works bit-for-bit and treats negatives no differently.
“What are the space rules?”
Constant extra space, which rules out the hash-set approach and points straight at XOR.
Let me confirm the setup: every value is paired except exactly one, and the array is non-empty.
A hash set would solve it in one pass but costs O(n) space.
Since the ask is constant space, I'll XOR everything — the pairs cancel and the answer falls out.
In plain words: combine every number with XOR. Anything that shows up twice contributes nothing, so what survives is the single unpaired value.
Worked example — nums = [4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) (reorder freely — XOR is commutative) = 4 ^ 0 ^ 0 = 4
x ^ x = 0. So each pair in the array annihilates itself the moment both copies are folded in — regardless of where they sit.
XOR is commutative and associative, so you can mentally regroup the numbers to place each pair side by side. That's why a single left-to-right sweep is enough — no sorting, no bookkeeping.
x ^ 0 = x, so starting an accumulator at 0 and XORing every element leaves exactly the unpaired value — the pairs having zeroed out along the way.
| Hash set | XOR | |
|---|---|---|
| Idea | Remember what you've seen; cancel on the second sighting | Fold every value into one accumulator |
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
Both take one pass; the difference is memory. The hash set carries up to n/2 values; XOR carries a single integer. Full code is in the Approaches selector below.
Key takeaway
When elements cancel in pairs and you need constant space, reach for XOR. Starting from 0 and XORing everything makes duplicates vanish (x ^ x = 0) and leaves the lone value behind. This "pairs cancel" reflex generalizes to a whole family of single-number puzzles.
ans = 0
for x in nums:
ans = ans XOR x
return ans