Single Number LeetCode Solution: The XOR Trick Explained

If there is one problem that perfectly captures the elegance of bit manipulation, it is Single Number (#136). Every element in the array appears exactly twice except for one. Find that single element. The constraint that makes this problem legendary: you must use O(1) extra space.

Single Number is the most solved Easy bit manipulation problem on LeetCode, and for good reason. The solution is a single line of code, runs in O(n) time with O(1) space, and relies on a property of XOR that feels like magic the first time you see it. This problem appears as a warm-up at companies like Amazon, Google, and Microsoft.

In this walkthrough, you will learn exactly why XOR solves this problem, see it work step by step on a real example, and understand how the same idea extends to harder variations like Single Number II and Missing Number.

The problem statement is beautifully simple. Given a non-empty array of integers nums, every element appears exactly twice except for one element that appears exactly once. Find that single one. You must implement a solution with linear runtime complexity and use only constant extra space.

The naive approach would use a hash set: iterate through the array, add elements you have not seen, remove elements you have seen before. The remaining element in the set is the answer. This works in O(n) time but uses O(n) space — violating the constraint.

You could also sort the array and compare adjacent pairs, but that takes O(n log n) time. The problem is specifically designed to push you toward a bit manipulation solution that achieves both O(n) time and O(1) space simultaneously.

The entire solution is this: XOR every element in the array together. The result is the single number. That is it. One pass through the array, one variable, no extra data structures.

Here is why this works. XOR has two critical properties. First, any number XORed with itself equals zero: a ^ a = 0. Second, any number XORed with zero equals itself: 0 ^ a = a. When you XOR all elements together, every number that appears twice cancels itself out to zero, and the single number XORed with that zero gives you the answer.

In Python, the solution is literally one line: return reduce(lambda a, b: a ^ b, nums). Or even cleaner with the operator module: return reduce(xor, nums). In any language, it is a simple loop that accumulates XOR across the array.

The magic of XOR goes deeper than just a ^ a = 0. XOR is both commutative and associative. Commutative means a ^ b = b ^ a — the order of operands does not matter. Associative means (a ^ b) ^ c = a ^ (b ^ c) — the grouping does not matter. Together, these properties mean you can rearrange the XOR of all elements in any order.

This is crucial because the duplicate elements are scattered throughout the array. You do not need them to be adjacent. Because XOR is commutative and associative, you can mentally regroup the operation so all pairs sit next to each other. Every pair becomes zero, and the single element remains.

Think of it like addition where every number has a negative counterpart except one. All the pairs cancel, and the lone survivor is your answer. XOR provides the same cancellation mechanism but works entirely at the bit level with no risk of overflow.

Let us trace through the example [4, 1, 2, 1, 2] step by step. Start with result = 0. XOR with 4: 0 ^ 4 = 4. XOR with 1: 4 ^ 1 = 5. XOR with 2: 5 ^ 2 = 7. XOR with 1: 7 ^ 1 = 6. XOR with 2: 6 ^ 2 = 4. The answer is 4.

Now look at it through the lens of regrouping. Because XOR is commutative and associative, we can rewrite 4 ^ 1 ^ 2 ^ 1 ^ 2 as (1 ^ 1) ^ (2 ^ 2) ^ 4. The first pair gives 0, the second pair gives 0, and 0 ^ 0 ^ 4 = 4. The duplicate pairs vanish and the unique element survives.

This works regardless of array size or element order. Whether the array has 3 elements or 3 million, the same principle applies: all pairs cancel to zero, and the single number is the final result.

The XOR approach handles every edge case gracefully. A single-element array returns that element immediately since 0 ^ a = a. Negative numbers work perfectly because XOR operates on the binary representation and the sign bit is just another bit. Large arrays with millions of elements still run in a single pass with a single integer of storage.

Time complexity is O(n) where n is the length of the array. You visit every element exactly once. Space complexity is O(1) — you only need one variable to store the running XOR result. No data structure can beat this combination for this problem.

One subtlety worth noting: the problem guarantees that exactly one element is unique. If the input violated this constraint — say two elements appeared once — the XOR result would be the XOR of those two unique elements, which is not useful on its own. The guarantee of exactly one unique element is what makes the XOR approach complete.

Single Number is more than just an interview warm-up. It is the foundation for an entire family of XOR-based problems. Single Number II (#137) asks the same question but every element appears three times except one — you solve it by counting bits modulo 3 instead of XOR. Single Number III (#260) has two unique elements, and you split them using a clever XOR partition.

Missing Number (#268) also uses XOR: XOR all indices 0 to n with all array elements, and the missing number survives. The same cancellation principle applies. Power of Two (#231) uses bit manipulation to check if exactly one bit is set. These problems form a connected web, and Single Number is the gateway.

Practice this problem until the XOR intuition is automatic. When you see "find the unique element" or "find what is missing," your first instinct should be XOR. Build that pattern recognition with tools like YeetCode flashcards so the connection is instant during interviews.