Single Number: The XOR Trick That Finds the Odd One Out
Solve Single Number in O(n) time and O(1) space using XOR — how bitwise cancellation works, a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Every element in the array shows up twice — except one. Find the loner. That's Single Number, and the naive instinct is to reach for a hash map to count occurrences. It works, but it burns O(n) extra memory to solve a problem that needs none.
The elegant answer uses one integer and a single bitwise operator. XOR everything together and the duplicates annihilate each other, leaving the unique value standing alone. No map, no sorting, no second pass.
This is the problem that teaches you to think in bits — and once the XOR cancellation clicks, you'll spot it in a dozen other places.
The problem
Given a non-empty array of integers nums where every element appears exactly twice except for one element that appears once, return that single element.
Input: nums = [4, 1, 2, 1, 2]
Output: 4 // 1 and 2 each appear twice; 4 is alone
Input: nums = [2, 2, 1]
Output: 1Two constraints in the prompt are the whole game:
- Every duplicate appears an even number of times (exactly twice), and the answer appears an odd number of times (exactly once).
- The follow-up asks for a solution with linear time and constant extra space — which quietly rules out the hash map most people write first.
The brute force baseline
The straightforward approach counts how many times each value appears, then returns the one with a count of one.
function singleNumber(nums) {
const counts = new Map();
for (const n of nums) {
counts.set(n, (counts.get(n) || 0) + 1);
}
for (const [value, count] of counts) {
if (count === 1) return value;
}
}This is O(n) time, which is fine. The problem is the O(n) space: the map grows to hold roughly half the array before any pair is confirmed. On a million-element input, you're allocating a hash table to answer a question that a single 32-bit integer can hold. The follow-up constraint exists precisely to push you off this solution.
The key insight: XOR cancels pairs
The exclusive-or operator (^) has three properties that stack into something powerful:
x ^ x = 0 // a value XOR'd with itself is zero
x ^ 0 = x // XOR with zero changes nothing
a ^ b ^ a = b // XOR is commutative and associative — order doesn't matterRead those together. If you XOR every number in the array into a running accumulator, each pair of equal values contributes x ^ x = 0 and vanishes. Because order doesn't matter, the duplicates don't even need to be next to each other — they find their partners no matter where they sit. What's left after everything cancels is 0 ^ single = single.
That's the reframe: you're not counting occurrences, you're toggling bits. A bit set by the first copy of a value gets unset by its second copy. Only the bits belonging to the lonely element survive.
The optimal solution
The visualizer implements exactly this — one accumulator, one loop, one XOR per element.
var singleNumber = function (nums) {
let result = 0;
for (let i = 0; i < nums.length; i += 1) {
result ^= nums[i]; // XOR cancelation
}
return result;
};result starts at 0 because it's the neutral element for XOR — folding in the first value leaves it unchanged (0 ^ nums[0] = nums[0]). Then each subsequent element toggles its bits into the accumulator. After the loop, every duplicate pair has cancelled to zero and result holds the single number. One pass, one variable.
Walkthrough
Tracing nums = [4, 1, 2, 1, 2]. Watch result — it wanders as pairs open and close, then lands exactly on 4 once every duplicate has been cancelled.
| Step | i | nums[i] | result (before) | operation | result (after) | binary |
|---|---|---|---|---|---|---|
| init | – | – | – | result = 0 | 0 | 000 |
| 1 | 0 | 4 | 0 | 0 ^ 4 | 4 | 100 |
| 2 | 1 | 1 | 4 | 4 ^ 1 | 5 | 101 |
| 3 | 2 | 2 | 5 | 5 ^ 2 | 7 | 111 |
| 4 | 3 | 1 | 7 | 7 ^ 1 | 6 | 110 |
| 5 | 4 | 2 | 6 | 6 ^ 2 | 4 | 100 |
| return | – | – | 4 | – | 4 | 100 |
Notice steps 2 and 4: the first 1 sets the low bit (100 → 101), and the second 1 clears it right back (111 → 110). Same story for 2 in steps 3 and 5. Every bit the duplicates touched returns to where it started. The only bits still standing at the end are 4's.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Hash map counting | O(n) | O(n) | stores up to n/2 distinct values |
| Sort then scan pairs | O(n log n) | O(1) | sorting dominates; then compare neighbors |
| XOR accumulator | O(n) | O(1) | one pass, a single integer of state |
The XOR solution reads each element once and does constant work per step — a single bitwise operation — so it's O(n) time. State is one integer regardless of input size, so O(1) space. It's the only approach that hits both halves of the follow-up constraint.
Common mistakes
- Initializing
resulttonums[0]and looping from index 1. This works, but it's easy to get the bounds wrong and skip or double-count an element. Starting at0and looping from index0is cleaner and can't misfire on a single-element array. - Reaching for a hash map by reflex. It passes, but fails the O(1)-space follow-up. Interviewers ask Single Number specifically to see if you know the XOR trick.
- Assuming the array must be sorted or the pairs adjacent. XOR is commutative —
[4,1,2,1,2]and[1,1,2,2,4]produce the identical result. Order never matters. - Trying to generalize XOR to "appears three times." This exact XOR-everything trick only works when duplicates appear an even number of times. Single Number II (every element appears three times except one) needs bit-counting per position, not a plain XOR fold.
Where this pattern shows up next
Single Number is your entry point into treating array problems as bit and pointer manipulation instead of bookkeeping:
- Remove Duplicates from Sorted Array — another in-place, O(1)-space pass where you overwrite instead of allocate.
- Remove Element — the two-pointer write technique that keeps extra space at zero.
- Reverse String — an in-place swap that, like XOR here, mutates a single structure with no scratch memory.
- Best Time to Buy and Sell Stock — a one-pass scan that tracks a single running value, just like
resulthere.
You can also step through Single Number interactively to watch each element's bits flip into the accumulator and see duplicate pairs cancel to zero in real time.
FAQ
Why does XOR find the single number?
XOR has two properties that combine perfectly here: any value XOR'd with itself is 0, and any value XOR'd with 0 is unchanged. When you fold every array element into one accumulator, each pair of equal numbers cancels to 0, and the lone element XOR'd against that accumulated 0 survives untouched. Because XOR is also commutative, the order of the elements — and whether duplicates are adjacent — makes no difference.
What is the time and space complexity of the XOR solution?
It's O(n) time and O(1) space. You scan the array exactly once, doing a single constant-time bitwise operation per element, so runtime grows linearly with input size. The only state is one integer accumulator, so extra memory stays constant no matter how large the array gets. That's what makes it strictly better than the O(n)-space hash map approach.
Does the XOR trick work if elements appear three times instead of twice?
No. Plain XOR only cancels values that appear an even number of times. If every duplicate appears three times (an odd count) except one unique element, XOR-ing them all together leaves leftover bits from the triples and gives a wrong answer. That variant — Single Number II — requires counting how many times each bit position is set across all numbers, modulo three, rather than a single XOR fold.
Do the numbers need to be sorted or the duplicates next to each other?
Neither. XOR is commutative and associative, meaning a ^ b ^ a equals a ^ a ^ b equals b. You can shuffle the array any way you like and the accumulator lands on the same result. This is exactly why the XOR solution beats a sort-then-scan approach: it skips the O(n log n) sorting step entirely and still handles duplicates scattered anywhere in the input.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.