Single Number — XOR Cancellation Every FAANG Interviewer Loves

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element appears twice except for exactly one element which appears once.

Input:  nums = [2, 2, 1]
Output: 1
Explanation: 2 appears twice and cancels out; 1 appears once and remains.

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

Why This Problem Matters#

Single Number appears in virtually every FAANG bit-manipulation question bank because it tests whether you know the XOR identity at interview speed. Most candidates who have not studied bit manipulation reach for a hash map — O(n) time and O(n) space, correct but not optimal. The interviewer is explicitly waiting to see if you can drop to O(1) space using XOR.

Beyond the interview context, understanding XOR cancellation is foundational for an entire category of problems: finding two unique numbers in an array of doubles, finding the missing number in a range, performing addition without the + operator, and generating Gray codes. If you understand why XOR solves Single Number — not just that it does — you will solve all variants on the fly without memorizing them.

The constraint "constant extra space" explicitly rules out hash maps, sorting, and counting arrays. If you freeze when a constraint eliminates your default approach you lose points. If you immediately pivot to bit manipulation you signal fluency.

The Core Insight#

XOR (exclusive OR) has two properties that make this problem trivial:

Identity: a ^ 0 = a — XOR-ing with zero leaves a number unchanged.

Self-cancellation: a ^ a = 0 — XOR-ing a number with itself produces zero.

XOR is also commutative and associative, so order of operations does not matter.

XOR every element into a single accumulator. Every element appearing twice contributes x ^ x = 0. The element appearing once contributes x ^ 0 = x. After processing all elements, the accumulator holds exactly the unique element.

Visual Dry Run#

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

Grouping duplicates: 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4. Each duplicate pair cancels to zero.

Solution (Optimal)#

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        result = 0
        for num in nums:
            result ^= num  # duplicates cancel: x^x=0; single survives: x^0=x
        return result

var singleNumber = function(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
};

Time: O(n) — single pass through the array Space: O(1) — one integer accumulator, no allocation

Common Mistakes#

• Reaching for a hash map without reading the space constraint. The problem explicitly requires O(1) space.
• Starting the accumulator at a non-zero value. XOR accumulator must start at 0 because 0 ^ a = a.
• Sorting first. Sorting brings duplicates together but costs O(n log n) time, violating the linear constraint.
• Confusing XOR with OR. a | a = a does not cancel, but a ^ a = 0 does.
• Forgetting that XOR works correctly on negative integers. No special cases are needed for sign in Python.

Interview Tips#

• State the XOR identities (a^a=0 and a^0=a) before writing code — this shows you know why it works.
• Mention the constraint check: hash map violates O(1) space, sorting violates O(n) time.
• Offer the follow-up variants proactively: three times (LC 137), two singles (LC 260), missing number (LC 268).

Follow-up Questions#

• What if every element appears three times except one? (LC 137) XOR alone fails because a^a^a = a. You need modulo-3 bit counting with two bitmasks (ones and twos).
• What if two elements appear once and the rest appear twice? (LC 260) XOR all to get a^b, isolate any set bit with x & (-x), partition the array by that bit, XOR each group independently.
• Can you find the single number in a stream? Yes — the XOR accumulator is inherently stream-friendly using O(1) space.
• Missing number in 0..n? (LC 268) XOR all array values with all indices 0..n; every index matching a value cancels, and the missing index survives.
• What is the time complexity lower bound? You must read every element at least once, so O(n) is optimal.

Key Takeaways#

• a ^ a = 0 is the self-cancellation identity that makes XOR uniquely suited for duplicate elimination.
• a ^ 0 = a is the identity element — starting the accumulator at 0 is not arbitrary, it is required.
• XOR is commutative and associative, so array order is irrelevant to the final result.
• A single-pass XOR accumulator is provably optimal: O(n) time and O(1) space simultaneously.
• The constraint "constant extra space" is the signal to reach for XOR, not hash maps.
• Internalizing these two identities unlocks an entire family of bit-manipulation problems without separate memorization.
• This exact pattern appears in LC 136, LC 268, LC 389, and forms the first phase of LC 260.