Single Number — XOR Bit Trick O(n) Time O(1) Space [Meta / Amazon Classic]

Problem Statement

Given a non-empty array of integers nums where every element appears exactly twice except for one element, return that single element. You must implement a solution with linear runtime complexity and use only constant extra space.

Example 1:

Input:  nums = [2, 2, 1]
Output: 1

Example 2:

Input:  nums = [4, 1, 2, 1, 2]
Output: 4

Note: The O(1) space constraint is the key restriction. It rules out the obvious hashmap approach and forces you toward a more elegant idea.

• Why This Problem Matters
• Three Approaches — Building Up to the "Wow" Answer
• Approach 1: Hash Map (O(n) time, O(n) space)
• Approach 2: Sort (O(n log n) time, O(1) or O(log n) space)
• Approach 3: XOR (O(n) time, O(1) space) — The Optimal Answer
• XOR Deep Dive — The Three Properties That Make It Work
• Property 1: Self-Cancellation — a ^ a = 0
• Property 2: Identity — a ^ 0 = a
• Property 3: Commutativity and Associativity — Order Does Not Matter
• The One-Sentence Summary
• Visual Dry Run — Tracing [4, 1, 2, 1, 2]
• The Escalation — How Interviewers Follow Up
• Single Number II — LeetCode 137
• Single Number III — LeetCode 260
• Common Mistakes
• Mistake 1: Forgetting Which XOR Property Does What
• Mistake 2: Wrong Initialization
• Mistake 3: Using a Hash Map When the Space Constraint Is Explicit
• Solutions
• Python
• JavaScript
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

Single Number is the canonical gateway to bit manipulation thinking in interviews. On the surface it looks like a frequency problem — just count occurrences. But the O(1) space requirement shuts down that path and demands you think differently.

The insight that unlocks it — XOR — is not something most engineers think about instinctively. When you produce the XOR solution in an interview, especially unprompted, it signals that you understand bitwise operations at a level beyond mere syntax. That is exactly why this problem (and its harder siblings LC 137 and LC 260) appear frequently at Meta, Amazon, and Google.

More importantly, XOR thinking is a transferable skill. Once you internalize the three XOR properties, you can solve a whole family of problems — finding missing numbers, detecting swaps, cryptographic checksums, parity checks — all with the same two-line loop.

Three Approaches — Building Up to the "Wow" Answer

Approach 1: Hash Map (O(n) time, O(n) space)

The most natural first instinct: count frequencies, return the key with count 1.

freq = {}
for num in nums:
    freq[num] = freq.get(num, 0) + 1
for num, count in freq.items():
    if count == 1:
        return num

Why it fails the constraint: The hash map stores up to n/2 distinct keys, which is O(n) space. The interviewer will immediately ask: "Can you do it in O(1) space?" This is the expected pivot point.

When it's acceptable: If the space constraint is not given — for example in a code review or a production setting where clarity matters more — the hashmap is perfectly readable and maintainable. Never dismiss it as "wrong"; it's just not optimal here.

Approach 2: Sort (O(n log n) time, O(1) or O(log n) space)

Sort the array, then scan pairs. After sorting, any duplicated number will always sit next to a copy of itself. So we check nums[i] against nums[i+1] in steps of two.

nums.sort()
for i in range(0, len(nums) - 1, 2):
    if nums[i] != nums[i + 1]:
        return nums[i]
return nums[-1]   # last element is the lone one

Why it's still not ideal: Sorting costs O(n log n) time, which is worse than O(n). Also, many sort implementations use O(log n) stack space. The interviewer is looking for the linear-time, constant-space solution.

Good as an intermediate step: Sorting shows you can think systematically. But when the interviewer follows up with "can you do better?", that's your cue.

Approach 3: XOR (O(n) time, O(1) space) — The Optimal Answer

XOR every element together and return the result. The duplicates cancel to zero; only the single element survives.

result = 0
for num in nums:
    result ^= num
return result

That's it. Two lines of logic. This is the answer that makes interviewers nod. To understand why it works, you need to deeply understand three XOR properties.

XOR Deep Dive — The Three Properties That Make It Work

XOR (exclusive OR) operates on individual bits: the output bit is 1 if the two input bits differ, 0 if they are the same. That binary definition gives rise to three algebraic properties that collectively make this problem trivial.

Property 1: Self-Cancellation — a ^ a = 0

Any number XORed with itself equals zero.

5 ^ 5:
  101
^ 101
-----
  000  = 0

Why? Because every bit in a is identical to the corresponding bit in a. XOR asks "are these bits different?" — the answer is always "no", so every output bit is 0.

This is the core cancellation mechanism. Every number that appears twice in the array will XOR with itself and vanish, contributing zero to the final result.

Property 2: Identity — a ^ 0 = a

Any number XORed with zero equals itself.

5 ^ 0:
  101
^ 000
-----
  101  = 5

Zero has all bits set to 0. XOR asks "are these bits different?" — every bit in a is compared against 0, so wherever a has a 1, the output is 1; wherever a has a 0, the output is 0. The result is identical to a.

This is why we initialize the accumulator to 0 — it is the neutral element for XOR, just as 0 is the neutral element for addition. Starting with result = 0 means the first XOR operation simply sets result to the first number, without distortion.

Property 3: Commutativity and Associativity — Order Does Not Matter

XOR is commutative: a ^ b = b ^ a XOR is associative: (a ^ b) ^ c = a ^ (b ^ c)

These two together mean we can reorder and regroup XOR operations freely. This is crucial because the array is not sorted — duplicates may not be adjacent.

Consider [4, 1, 2, 1, 2]. Rewriting using commutativity and associativity:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)   ← regroup pairs using associativity
= 4 ^ 0 ^ 0               ← pairs cancel via Property 1
= 4                        ← identity via Property 2

The order of elements in the array does not matter at all. Every duplicate pair will cancel no matter where its two instances sit in the sequence.

The One-Sentence Summary

XOR all numbers together. Every number that appears twice cancels to 0. The lone number remains.

Visual Dry Run — Tracing [4, 1, 2, 1, 2]

Let's walk through the algorithm step by step, showing the intermediate result value in both decimal and binary after each XOR operation.

Initial:  result = 0         (binary: 000)

Step 1:   result ^= 4
          0 ^ 4 = 4          (000 ^ 100 = 100)
          result = 4

Step 2:   result ^= 1
          4 ^ 1 = 5          (100 ^ 001 = 101)
          result = 5

Step 3:   result ^= 2
          5 ^ 2 = 7          (101 ^ 010 = 111)
          result = 7

Step 4:   result ^= 1
          7 ^ 1 = 6          (111 ^ 001 = 110)
          result = 6          ← the first "1" just cancelled with the second "1"

Step 5:   result ^= 2
          6 ^ 2 = 4          (110 ^ 010 = 100)
          result = 4          ← the first "2" just cancelled with the second "2"

Final answer: 4

Notice what happened in steps 4 and 5: the two occurrences of 1 cancelled each other out, and then the two occurrences of 2 cancelled each other out — even though they were not adjacent in the array. The commutative and associative properties did that work for us invisibly.

The bit-level view makes it concrete: after step 5, only bit 2 (value 4) remains set, which is exactly the unpaired number.

The Escalation — How Interviewers Follow Up

Once you nail LC 136, a strong interviewer will escalate. Here is the common progression:

Single Number II — LeetCode 137

Every element appears exactly 3 times except one. Find the single element. O(n) time, O(1) space.

XOR alone no longer helps because a ^ a ^ a = a, not 0. You need a 3-state counter for each bit.

The key insight: count the occurrences of each bit across all numbers, then take each count modulo 3. If a bit's count mod 3 is 1, that bit belongs to the single element.

The elegant implementation uses two accumulators, ones and twos, that together act as a 2-bit counter (counting 0, 1, 2, then resetting to 0 at 3):

def singleNumberII(nums):
    ones, twos = 0, 0
    for num in nums:
        ones = (ones ^ num) & ~twos   # add to 'ones' if not already in 'twos'
        twos = (twos ^ num) & ~ones   # add to 'twos' if not already in 'ones'
    return ones

After processing all elements, ones holds the bits that appeared exactly once — the answer. The triplets have been counted to 3 and reset to 0 by the mod-3 logic.

The interview escalation signal: If you solved LC 136 by explaining XOR properties, the interviewer may jump straight here to test whether you can generalize the bit-manipulation thinking. The answer is not "use a hashmap" — it is "design a bit-level counter."

Single Number III — LeetCode 260

Two elements appear exactly once. All others appear twice. Return both single elements. O(n) time, O(1) space.

This is a genuinely hard escalation. The approach:

1. XOR all elements to get xor_all = a ^ b (all duplicates cancel, leaving the XOR of the two unique numbers).

2. Find a bit where a and b differ. Since a != b, xor_all != 0, so at least one bit is set. The rightmost set bit is found with: diff_bit = xor_all & (-xor_all) (using two's complement negation to isolate the lowest set bit).

3. Partition all numbers into two groups by whether that bit is set or not. Because a and b differ at that bit, they land in different groups. All duplicates land in the same group as each other (and cancel out within their group).

4. XOR within each group to isolate a and b separately.

def singleNumberIII(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n              # xor_all = a ^ b

    diff_bit = xor_all & (-xor_all)   # rightmost bit where a and b differ

    a = 0
    for n in nums:
        if n & diff_bit:          # group by the differing bit
            a ^= n
    return [a, xor_all ^ a]       # b = (a ^ b) ^ a

The clever use of xor_all ^ a to recover b at the end — rather than XORing through the second group separately — is a clean touch worth mentioning in an interview.

Common Mistakes

Mistake 1: Forgetting Which XOR Property Does What

The three properties are distinct and all three are needed. Forgetting that XOR is associative leads to thinking "the duplicates must be adjacent for this to work" — they don't. Forgetting the identity property leads to initializing result to something other than 0, corrupting the first element.

Mistake 2: Wrong Initialization

# WRONG — initializing to nums[0] double-counts the first element
result = nums[0]
for num in nums[1:]:
    result ^= num

Always initialize to result = 0. Zero is the identity element; it has no effect on the first XOR operation.

Mistake 3: Using a Hash Map When the Space Constraint Is Explicit

If the problem says "constant extra space," a hashmap is not a valid solution. Even if it gives the correct output, you will lose points in an interview for not meeting the stated constraint. Always re-read the constraints and let them guide your approach selection.

Solutions

Python

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # --- Approach 1: Hash Map (O(n) space — violates constraint) ---
        # freq = {}
        # for num in nums:
        #     freq[num] = freq.get(num, 0) + 1
        # return next(k for k, v in freq.items() if v == 1)

        # --- Approach 2: XOR (O(1) space — optimal) ---
        # Initialize to 0 (identity element: 0 ^ x = x)
        result = 0
        for num in nums:
            result ^= num   # pairs cancel to 0; lone element survives
        return result

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */

// --- Approach 1: Hash Map (O(n) space) ---
function singleNumberHashMap(nums) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    for (const [num, count] of freq) {
        if (count === 1) return num;
    }
}

// --- Approach 2: XOR (O(1) space — optimal) ---
function singleNumber(nums) {
    // reduce accumulates XOR across all elements.
    // Pairs cancel (a ^ a = 0); lone element survives (x ^ 0 = x).
    return nums.reduce((result, num) => result ^ num, 0);
}

Complexity Analysis

The XOR solution makes a single pass through the array and uses only one integer of extra storage (result), regardless of input size.

Follow-up Questions

Q1: What if every element appeared 3 times except one? (LC 137) Count bits mod 3. Use the ones/twos two-accumulator state machine to avoid O(n) space. Time O(n), space O(1).

Q2: What if two elements appeared exactly once? (LC 260) XOR everything to get a ^ b. Isolate the rightmost differing bit with xor & -xor. Use that bit to partition numbers into two groups. XOR within each group to isolate a and b. Time O(n), space O(1).

Q3: Can you find the missing number in [0..n] in O(1) space? (LC 268) Yes — XOR all numbers in [0..n] with all numbers in the array. Duplicates cancel; the missing number survives. Alternatively, use the arithmetic sum formula n*(n+1)/2 - sum(nums).

Q4: What if elements could appear 0, 1, or 2 times and you needed all unique elements? Now XOR breaks down — a number appearing 0 times and a number appearing 2 times both contribute 0. You need a different approach (hashmap or sort).

This Pattern Solves

Any time you see "find the odd one out" in a sea of pairs, reach for XOR first.

Key Takeaway

The XOR solution works because of three algebraic properties: any number XORed with itself is 0 (cancellation), any number XORed with 0 is itself (identity), and XOR is commutative and associative (order is irrelevant). Together these guarantee that all duplicates cancel and the lone element is all that remains. Recognizing when to apply XOR — specifically when the problem involves pairing, cancellation, or difference at the bit level — is what separates engineers who just know algorithms from engineers who understand them.

Next: Problem 10 — Intersection of Two Arrays II →