Single Number LeetCode 136 Deep Dive

LeetCode 136 — Single Number — gives you a non-empty array of integers where every element appears exactly twice except for one element which appears exactly once. Your task is to find and return that single element. The problem carries two hard constraints: your solution must run in O(n) time and use only O(1) extra space.

These two constraints rule out the most intuitive approaches. A hash map or hash set that tracks counts runs in O(n) time but uses O(n) space. Sorting runs in O(1) extra space but costs O(n log n) time. The constraints force you toward a bit-level insight: XOR, a bitwise operation with exactly the properties needed to cancel pairs and expose the singleton.

Single Number is the canonical entry point into bit manipulation interview problems. It demonstrates that bitwise operators are not just low-level curiosities but powerful algorithmic tools that can replace entire data structures when the problem structure aligns with their mathematical properties.

The XOR solution is elegant: initialize a variable result = 0, then XOR every element in the array into result. When you finish, result holds the single number. The entire solution is one line: return reduce(xor, nums) in Python or a simple loop with ^= in Java. No extra memory, no sorting, one pass.

Why does this work? XOR has two critical properties: a^a = 0 (any number XOR-ed with itself is zero) and a^0 = a (any number XOR-ed with zero is itself). Because XOR is also commutative and associative, the order of operations does not matter. Every pair of identical elements XORs to 0, and 0 XOR-ed with the unique element leaves the unique element.

Concretely: XOR-ing the entire array is equivalent to computing pair1^pair1 ^ pair2^pair2 ^ ... ^ single = 0 ^ 0 ^ ... ^ single = single. The pairs vanish and the singleton survives. This is why XOR is sometimes called a self-inverse operation — it undoes itself on repeated elements.

XOR (exclusive OR) is a bitwise operation that outputs 1 for each bit position where the two input bits differ, and 0 where they are the same. At the integer level, XOR combines all bit positions independently. The properties that make it useful for Single Number emerge directly from this per-bit behavior.

Self-inverse: a^a = 0 for every integer a, because every bit position of a matches itself, producing 0. Identity: a^0 = a for every integer a, because 0 contributes no differing bits. Commutativity: a^b = b^a because bit comparison is symmetric. Associativity: (a^b)^c = a^(b^c) because each bit position is computed independently.

When you XOR every element of the array together, the commutative and associative laws let you mentally reorder the computation so that each duplicate pair is adjacent. Every adjacent pair cancels to 0. Chaining all those zeros together and XOR-ing the unique element with 0 gives you the unique element. The math is: result = 0 XOR x1 XOR x1 XOR x2 XOR x2 XOR ... XOR single = single.

HashSet approach: iterate the array; if an element is not in the set, add it; if it is already in the set, remove it. At the end the set contains exactly one element — the single number. Time complexity O(n), space complexity O(n). This is intuitive but violates the O(1) space constraint of the problem.

Math approach: compute 2 * sum(set(nums)) - sum(nums). If every element appeared twice, 2*sum(set) would equal sum(nums). The difference is exactly the single number. Requires converting nums to a set to get unique values. Time O(n), space O(n) for the set. Clever but still uses extra space.

Sorting approach: sort the array, then scan pairs (nums[0],nums[1]), (nums[2],nums[3]), etc. The first pair that does not match has the single number at the first index. Time O(n log n), space O(1) or O(log n) depending on the sort algorithm. Violates the O(n) time constraint.

Consider nums = [4, 1, 2, 1, 2]. Initialize result = 0. XOR each element: 0^4 = 4, 4^1 = 5, 5^2 = 7, 7^1 = 6, 6^2 = 4. The final result is 4, which is the single number. Every other element (1 and 2) appeared twice and cancelled itself out.

Notice that the pairs do not need to be adjacent in the array. Commutativity and associativity mean the result is the same regardless of element order. You could shuffle [4, 1, 2, 1, 2] into any arrangement and still get 4. The XOR accumulator does not care about position — only about which values appear an odd versus even number of times.

For a single-element array nums = [7], the result is 0^7 = 7. The XOR of an array with one element is the element itself, which is the correct answer by definition. The algorithm handles this edge case naturally without any special-casing.

Python one-liner using functools.reduce: from functools import reduce; from operator import xor; return reduce(xor, nums). This folds XOR across the entire list in a single expression. Alternatively, use an explicit loop: result = 0; for n in nums: result ^= n; return result. Both are O(n) time O(1) space.

Java explicit loop: public int singleNumber(int[] nums) { int result = 0; for (int n : nums) { result ^= n; } return result; } The ^= operator is XOR-assign. No imports needed, no extra data structures. The loop body is one line and the total method is five lines including braces.

Both implementations share the same structure: initialize an accumulator to 0, XOR every element into it, return the accumulator. The time complexity is O(n) because every element is visited exactly once. The space complexity is O(1) because only one integer variable is used regardless of input size.

Missing Number (LeetCode 268) is a direct XOR variant: XOR all indices 0..n with all elements. The one index that has no matching element remains. This is the same self-cancellation trick applied to a range rather than a duplicate array. It generalizes the Single Number insight to a different problem shape.

Single Number II (LeetCode 137) generalizes the problem: every element appears three times except one. A plain XOR accumulator no longer works. The solution uses two accumulators (ones and twos) that together implement a 2-bit counter for each bit position, advancing through states 0 -> 1 -> 2 -> 0. When the count hits 3 the bit resets, leaving only bits from the element that appeared once.

Number of 1 Bits (LeetCode 191) and Reverse Bits (LeetCode 190) develop fluency with the shift-and-mask technique. Counting Set Bits uses n & (n-1) to clear the lowest set bit. Single Number, Missing Number, and the Number of 1 Bits family are the three starter clusters of bit manipulation problems that every interviewer draws from for medium-difficulty rounds.