Single Number
Single Number: every element in nums appears twice except for one, which appears once. Return that single element using constant extra space and linear time.
- 1 <= nums.length <= 3 * 10⁴
- -3 * 10⁴ <= nums[i] <= 3 * 10⁴
- Each element in the array appears twice except for one element which appears only once.
Intuition
Single number leetcode problem 136: every element appears twice except one, which appears once. The constraints demand linear time and constant space, which rules out both sorting and a hash set.
The solution rests on three properties of XOR:
- A number XORed with itself is 0, a number XORed with 0 is itself, and XOR is commutative and associative — so order does not matter.
Taken together, XORing every element cancels each pair to zero and leaves the unpaired value standing alone.
That is the entire algorithm: fold XOR across the array starting from 0, and return the result. No conditionals, no data structure, no second pass.
The commutativity is what makes the array's order irrelevant — pairs need not be adjacent, and the array need not be sorted. That is the property people most often fail to notice, and it is why the solution is a single loop rather than something more careful.
Starting the accumulator at 0 matters, since 0 is XOR's identity. Starting at nums[0] and looping from index 1 also works, but starting at 0 is cleaner and handles a single-element array uniformly.
A hash map counting occurrences is correct but uses O(n) space, and sorting then scanning for the unpaired neighbour is O(n log n). Both are rejected by the stated constraints, which is the point of the problem.
The technique extends: Single Number III has two unique values and splits them by a differing bit; Single Number II has elements appearing three times and needs bit counting modulo 3, since XOR only cancels pairs.
One pass gives O(n) time and O(1) space.
XOR is its own inverse and commutative, so every pair cancels regardless of position and the lone value falls out. Constant space, one pass, no hash map. Whenever elements cancel in pairs, XOR is worth reaching for before counting.
Approach
Before reading on: price up what counting everything costs here, then ask which operator makes the unwanted values cancel themselves out. Aim for O(n) time and O(1) space.
Read the constraints
Linear time and constant space rule out sorting and hash sets. That combination is what points at bit manipulation.
Use XOR's self-cancellation
A value XORed with itself is 0, so every pair vanishes. The unpaired element is all that survives the fold.
Rely on commutativity
XOR is order-independent, so pairs need not be adjacent and the array need not be sorted — which is why one simple loop suffices.
Start the accumulator at zero
0 is XOR's identity, so it does not affect the result. Starting there handles a single-element array without a special case.
Fold across the array
XOR every element into the accumulator and return it. No conditionals, no auxiliary structure, no second pass.
Know where XOR stops working
XOR only cancels pairs. Single Number II has triples and needs bit counting modulo 3; Single Number III has two uniques and splits on a differing bit.
Cost of the approach
One pass with a single accumulator gives O(n) time and O(1) space, exactly as the constraints require.
Solution & live demo
Common pitfalls
Using a hash map or set
seen = set()
for n in nums:
if n in seen: seen.remove(n)
else: seen.add(n)for n in nums:
ans ^= nCorrect, but the problem asks for O(1) extra space. XOR carries the same information in a single integer because pairing is exactly what it encodes.
Starting the accumulator at the first element and re-XORing it
ans = nums[0]
for n in nums:
ans ^= nans = 0
for n in nums:
ans ^= nnums[0] gets folded in twice and cancels itself, so the result is the XOR of everything except the first element. Starting at 0 is safe because 0 is XOR's identity.
Applying it when elements repeat three times
ans ^= n # for the 'appears three times' variant
# count set bits mod 3 instead
XOR cancels in pairs, so a value appearing three times survives once and corrupts the result. The odd-count variants need per-bit counting modulo that count.
Edge cases
0 ^ 7 = 7. The loop runs once and returns the only element, which is by definition the single number.
XOR operates on the two's-complement bit pattern, so signs are handled automatically. -3 ^ -3 is still 0.
Works: 1 ^ 1 ^ 0 = 0. Because we return the accumulator rather than checking for a sentinel, a legitimate 0 answer is indistinguishable from no answer only if the input were empty — which the constraints forbid.