Single Number Solution

Problem

Every element in the array appears exactly twice except for one element, which appears exactly once. Return that element without using extra memory.

Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: 1 and 2 each appear twice; 4 appears once.

Counter-example: [2, 2, 3, 3, 5] → 5 (order doesn't matter — any arrangement of the pairs produces the same answer).

Intuition

XOR has two key properties: a number XOR'd with itself equals zero (a ^ a = 0), and zero XOR'd with any number is that number (0 ^ a = a). When we XOR every element together, the duplicate pairs all cancel to zero and the unique element is all that remains.

Approach 1 — Hash Map

Count how many times each number appears, then return the one with a count of exactly 1.

Create an empty frequency map.
Iterate through the array, incrementing each number's count.
Scan the map and return the number whose count is 1.

1def singleNumber(nums: list[int]) -> int:
2    frequency = {}
3    for num in nums:
4        frequency[num] = frequency.get(num, 0) + 1
5    return next(num for num, count in frequency.items() if count == 1)

Time: O(n) — one pass to build the map, one pass to scan it.
Space: O(n) — the map holds at most n/2 + 1 distinct values.

Approach 2 — XOR

XOR every element together in a single pass; all pairs self-destruct and only the unique element remains.

Initialize result to 0.
For each number in the array, XOR it into result.
Return result.

1def singleNumber(nums: list[int]) -> int:
2    result = 0
3    for num in nums:
4        result ^= num  # paired elements cancel to zero, unpaired element survives
5    return result

Time: O(n) — one pass through the array.
Space: O(1) — only a single integer accumulator.

Complexity Summary

Approach	Time	Space	When to use
Hash Map	O(n)	O(n)	When the problem doesn't restrict extra memory
XOR	O(n)	O(1)	Canonical solution — satisfies the follow-up constant-space constraint

Common Mistakes

Using bitwise AND or OR instead of XOR — AND accumulates only bits set in every element, and OR accumulates all set bits; neither cancels duplicates. XOR is the only bitwise operator that makes equal values vanish.
Sorting first to find the odd one out — scanning adjacent pairs after sorting works but costs O(n log n), which violates the linear-time expectation interviewers have for this problem.
Forgetting that XOR is both commutative and associative — element order in the array doesn't matter; the result is the same regardless of traversal order, so no sorting or indexing tricks are needed.
For the hash map approach: using a try/except or an if key in dict check — dict.get(key, 0) + 1 is the idiomatic one-liner for counting; the longer alternatives add noise without clarity.
Assuming negative numbers break XOR — they don't; XOR operates on the raw two's-complement bit pattern, so it cancels negative duplicates just as cleanly as positive ones.

Single Number — Solution