Single Number — The XOR Trick Explained

The Single Number problem gives you a non-empty array where every element appears exactly twice, except for one element that appears once. Return that single element. The follow-up requires linear time and constant extra space.

The Problem

You receive nums, a non-empty array of integers where exactly one value appears once and every other value appears exactly twice. Return the singleton.

Example: nums = [4, 1, 2, 1, 2] returns 4.

Intuition

The simplest approach uses a hash map of counts: O(n) time but O(n) space. A sort-based approach is O(n log n) and mutates input. Neither passes the follow-up’s O(1) space constraint.

XOR has three properties we need: it is commutative, associative, and x ^ x = 0 while x ^ 0 = x. If we XOR every element of the array together, the pairs cancel and we are left with the single unpaired value. Order does not matter, which is why the one-pass loop works regardless of how the duplicates are arranged. Total work is O(n) with a single accumulator variable — O(1) extra space.

XOR never overflows in fixed-width languages because it does not carry. That is a small but real advantage over solutions based on summation.

Explanation with Example

Take nums = [4, 1, 2, 1, 2]. We XOR them in order.

If you re-order the input as [1, 1, 2, 2, 4], you can see the cancellation more cleanly: 1 ^ 1 = 0, then 0 ^ 2 ^ 2 = 0, then 0 ^ 4 = 4. The XOR does not care about ordering.

step 0: result = 0
step 1: 0 ^ 4 = 4
step 2: 4 ^ 1 = 5
step 3: 5 ^ 2 = 7
step 4: 7 ^ 1 = 6
step 5: 6 ^ 2 = 4   <- the answer

Code

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int x : nums) result ^= x;
        return result;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int x : nums) result ^= x;
        return result;
    }
};

Edge Cases

• An array of length 1 returns its only element, because 0 ^ x = x.
• The problem guarantees exactly one unpaired value, so we do not need to handle the case where all values appear twice.
• Negative numbers are fine since integer XOR works on the two’s-complement representation seamlessly.

Complexity Analysis

Time complexity is O(n): a single pass through the array, constant work per element. Space complexity is O(1): just the accumulator variable. We do not allocate any auxiliary structure, regardless of input size. This is the tightest possible bound — you have to look at each element at least once to know it is the unpaired one.

How to Explain It in an Interview

Begin by stating the property: x ^ x = 0. That alone gives away the punchline. Then say: since every paired element cancels itself and XOR is order-independent, accumulating XOR across the whole array leaves the unpaired element. Write the loop, run through a tiny example like [2, 2, 1], and finish with the complexity statement.

If the interviewer pushes for follow-ups, mention Single Number II (every element appears three times, one appears once — bitwise counting modulo 3) and Single Number III (two singletons — XOR the whole array to get a ^ b, then use any set bit of a ^ b to partition the input into two groups, each of which reduces to the original problem). Both follow-ups build on the same insight.

Related Problems

• Single Number II — modulo 3 bit counting.
• Single Number III — XOR partitioning.
• Missing Number — XOR cancellation across a range.
• Find the Difference — XOR over characters of two strings.