You're given a non-empty integer array nums where every element appears exactly twice, except for one element that appears exactly once. Find and return that single element.
Your solution should run in linear time and use only constant extra space (no hash map or counting structure).
Example
Constraints
- 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 exactly once.
Intuition
A first pass just counts how many times each value shows up — tally every element in a hash map, then scan the tallies for the one value whose count is 1.
function singleNumber(nums) {
// Tally how many times each value shows up.
const counts = new Map();
for (const num of nums) {
counts.set(num, (counts.get(num) || 0) + 1);
}
// The one value with a count of 1 never got paired up — return it.
for (const [num, count] of counts) {
if (count === 1) return num;
}
}This already runs in O(n) time, but it spends O(n) extra space on the hash map — exactly what the problem rules out ("no hash map or counting structure", "constant extra space"). Can we do better?
The key observation is XOR: it's self-cancelling (x ^ x = 0) and identity-preserving (x ^ 0 = x). Folding every element through a single running XOR value, order doesn't matter (XOR is commutative and associative) — every value that appears twice cancels itself back out, leaving only the value that appeared once. That's this chapter's XOR fold technique from the intro: one integer standing in for the whole hash map, no structure to store counts in at all.
The stored solution's variable name already matches this walkthrough — result is the running XOR value — so no bridging is needed.
Walking it through:
nums = [8, 3, 8, 5, 3] — result = running XOR fold
Start folding: the running result picks up the first value untouched.
3 hasn't been seen yet, so it folds straight in — result is now 11, a value that doesn't even appear in the array.
The second 8 cancels the first (8 ^ 8 = 0), stripping it back out — result drops back to 3, the pending value from before.
5 only appears once total, so it folds in and stays — nothing will cancel it later.
The second 3 cancels the first (3 ^ 3 = 0), leaving only the 5 that was folded in earlier. Loop ends: return 5.
Optimization
XOR fold
XOR is commutative, associative, self-cancelling (x ^ x = 0), and identity-preserving (x ^ 0 = x). Folding every element through XOR in one pass, order doesn't matter and every duplicated pair cancels itself out (x ^ x = 0), leaving only the value that appeared once. JavaScript's ^ operator coerces both operands to signed 32-bit integers, which the constraint range (|nums[i]| <= 3 * 10^4) comfortably fits inside, so negative values fold correctly too.
O(n) time, O(1) extra space — no hash map or counting structure needed.
function singleNumber(nums) {
// Fold every value through XOR; equal values cancel out (x ^ x = 0).
let result = 0;
for (const num of nums) {
result ^= num; // order doesn't matter — a value's pair cancels it whenever it's seen
}
// Whatever's left never got cancelled — that's the value that appeared once.
return result;
}Complexity analysis
Time complexity: O(n). Here's why:
- The loop visits each of the
nelements exactly once. - Each step does one O(1) XOR and reassignment.
So the whole fold is a single linear pass — O(n) — matching the brute force's time bound, but without ever building a supporting structure.
Space complexity: O(1). Here's why:
- Only the single
resultaccumulator (and the loop variable) are kept, regardless of the input's length. - Unlike the brute force's hash map, which grows to hold up to
n / 2 + 1entries in the worst case, nothing here scales with the input.
So the XOR fold uses O(1) auxiliary space — meeting the constant-space requirement the brute force couldn't.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [9] | 9 | Single-element array — the one value is automatically the answer. |
| nums = [4,4,0] | 0 | 0 is the unpaired value; XOR's identity property (x ^ 0 = x) lets it pass through the fold untouched while the 4/4 pair cancels out. |
| nums = [5,5,2,2,3] | 3 | Two duplicate pairs, with the single value sitting at the end. |
| nums = [-2,-2,-7] | -7 | Negative values fold the same way — XOR treats the sign bit like any other bit. |
| nums = [1,1,2,2,3,3,4] | 4 | Three duplicate pairs before the single value, confirming the fold generalizes beyond one pair. |
Try it yourself
Write your solution against the real judge before checking the reference.