Missing Number — 4 Approaches, XOR Deep Dive & Interview Trade-offs [LC 268]

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing.

Example 1: nums = [3, 0, 1] → 2 Example 2: nums = [0, 1] → 2 Example 3: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8

Constraints:

• n == nums.length
• 1 <= n <= 10⁴
• 0 <= nums[i] <= n
• All numbers in nums are unique

• Why This Problem Matters
• Approach 1 — Sort
• Idea
• Why it works
• Walk-through on [3, 0, 1]
• Complexity
• Limitation
• Approach 2 — HashSet
• Idea
• Walk-through on [3, 0, 1]
• Complexity
• Limitation
• Approach 3 — Gauss Formula
• Idea
• Walk-through on [3, 0, 1]
• Complexity
• Limitation
• Approach 4 — XOR
• Idea
• Complexity
• Deep Dive — Why XOR Actually Works
• Why this reveals bit manipulation thinking
• The Integer Overflow Note
• Visual Dry Run — [3, 0, 1]
• Gauss approach
• XOR approach (single-loop form)
• Common Mistakes
• 1. Integer overflow in the Gauss formula
• 2. Wrong XOR initialization
• 3. Off-by-one in the range
• Solutions
• Python
• JavaScript
• Complexity Analysis
• Follow-up Questions
• LC 287 — Find the Duplicate Number
• LC 448 — Find All Numbers Disappeared in an Array
• LC 41 — First Missing Positive
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

At first glance, LC 268 looks like a warm-up throwaway. It is rated Easy. You could solve it in one line of Python. So why does it show up in Meta, Amazon, and Google phone screens?

Because interviewers are not testing whether you can find the missing number. They already know you can. What they are testing is whether you can identify multiple valid approaches, reason about their trade-offs, and adapt under progressive constraints.

The progression typically looks like this:

1. "Solve it however you like." → Sort or HashSet gets you through.
2. "Now do it in O(n) time." → Forces you off sort.
3. "Now do it in O(1) space." → Forces you off HashSet, pushes you to math or XOR.
4. "Now do it without using any arithmetic formulas — no multiplication, no division." → Forces you to XOR.
5. "What if the numbers could overflow a 32-bit integer?" → Gauss fails; XOR wins.

Each constraint peels away one approach. A candidate who only knows the Gauss formula gets stuck at step 4. A candidate who knows all four — and can explain why XOR is immune to overflow — demonstrates the kind of layered thinking that distinguishes senior engineers from new grads.

Let us build every approach from scratch.

Approach 1 — Sort

Idea

If the array were sorted, the number at index i should equal i. The first index where nums[i] != i tells you the missing number. If no gap is found before the end, n itself is missing.

Why it works

In a complete range [0, n], a sorted array satisfies nums[i] = i for every position. A missing element breaks that alignment for the first time at the gap.

Walk-through on [3, 0, 1]

After sorting: [0, 1, 3]

Complexity

• Time: O(n log n) — dominated by the sort
• Space: O(1) — in-place sort (depends on sort algorithm; Python's Timsort is O(n))

Limitation

Fails the "O(n) time" constraint. Eliminated first.

Approach 2 — HashSet

Idea

Store all array values in a set. Then iterate 0 through n and return the first value not in the set.

Walk-through on [3, 0, 1]

Set: {3, 0, 1}

Check 0 → present. Check 1 → present. Check 2 → not present, return 2.

Complexity

• Time: O(n) — one pass to build the set, one pass to check
• Space: O(n) — the set holds all n elements

Limitation

Fails the "O(1) space" constraint. Eliminated second.

Approach 3 — Gauss Formula

Idea

The sum of all integers from 0 to n is given by the Gauss formula: n * (n + 1) / 2. The missing number is simply the difference between this expected sum and the actual sum of the array.

missing = expected_sum - actual_sum
        = n*(n+1)/2 - sum(nums)

Walk-through on [3, 0, 1]

• n = 3
• expected = 3 * 4 / 2 = 6
• actual = 3 + 0 + 1 = 4
• missing = 6 - 4 = 2

Complexity

• Time: O(n) — one pass for the sum
• Space: O(1) — only two variables

Limitation

Integer overflow. For large n, n * (n + 1) can exceed the range of a 32-bit signed integer (max ~2.1 billion). With n = 10⁴, the product is 10⁸, which is still safe. But in a general or modified version of this problem with n up to 10⁵ or beyond, or in C/Java without long, you must cast carefully. Interviewers will probe this. XOR sidesteps this entirely.

Approach 4 — XOR

Idea

XOR has two crucial properties:

• a ^ a = 0 — any value XORed with itself cancels to zero
• a ^ 0 = a — any value XORed with zero is unchanged
• XOR is commutative and associative — order does not matter

Strategy: XOR together every index from 0 to n, then XOR in every value from the array. Every number that is present in the array appears once as an index and once as a value, so it XORs with itself and cancels to zero. The missing number appears only once (as an index), so it never gets cancelled. It is the only value left standing.

result = 0
for i in range(n+1):     # XOR all indices 0 through n
    result ^= i
for num in nums:          # XOR all array values
    result ^= num
return result

Or more elegantly as a single loop:

result = n                # start with n itself (it has no pair yet)
for i, num in enumerate(nums):
    result ^= i ^ num
return result

Complexity

• Time: O(n) — one pass
• Space: O(1) — one integer variable
• No overflow possible — XOR operates bitwise; no arithmetic accumulation

Deep Dive — Why XOR Actually Works

Let us use [3, 0, 1] as a concrete example and trace every XOR operation.

We need to XOR the indices {0, 1, 2, 3} with the values {3, 0, 1}.

Think of it as two multisets being merged: {0, 1, 2, 3} from indices, and {0, 1, 3} from values. Every number that appears in both sets XORs with itself and disappears. The number 2 appears in the index set but not in the value set. It has no partner. It survives.

Formally:

0 ^ 1 ^ 2 ^ 3       (all indices 0..n)
^ 3 ^ 0 ^ 1         (all values)

= (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2
= 0 ^ 0 ^ 0 ^ 2
= 2

The key insight: XOR is its own inverse. If you XOR a value in twice, it vanishes. The missing number only appears once across the combined set, so it cannot vanish.

This is the same fundamental trick used in Single Number (LC 136), but applied across two sequences instead of one. If you understood Single Number through XOR, Missing Number is a natural extension.

Why this reveals bit manipulation thinking

A developer who reaches for XOR here is not just solving the problem — they are demonstrating that they think in terms of algebraic group structure. The integers under XOR form an abelian group where every element is its own inverse. Finding the missing element is equivalent to finding the identity residue after pairing.

Interviewers from companies like Meta specifically look for this kind of reasoning because it transfers directly to problems in compression, error correction codes, cryptography, and hardware design.

The Integer Overflow Note

Let us be precise about when Gauss overflows.

In a 32-bit signed integer, the maximum value is 2^31 - 1 = 2,147,483,647. The Gauss formula computes n * (n + 1) / 2. For n = 65,536, n * (n + 1) = 4,295,032,832, which exceeds the 32-bit limit.

In Java and C/C++, you must cast to long before the multiplication:

long expected = (long) n * (n + 1) / 2;

In Python, integers have arbitrary precision, so overflow is never an issue. In JavaScript, numbers are 64-bit floats and are safe up to 2^53.

XOR never overflows — it is a bitwise operation on fixed-width integers. The result is always within the same bit width as the inputs. This is why XOR is strictly more robust than the Gauss approach for general inputs.

Visual Dry Run — [3, 0, 1]

Gauss approach

n = 3
expected = 3 * 4 / 2 = 6

actual_sum = 3 + 0 + 1 = 4

missing = 6 - 4 = 2  ✓

XOR approach (single-loop form)

Start with result = n = 3.

Final result: 2. Correct.

Notice that at each step we are simultaneously pairing index i with value num. Index 0 pairs with value 3, index 1 pairs with value 0, index 2 pairs with value 1. Only index 3 (represented by our initial result = n = 3) has no partner value — its pair 3 cancelled in the first iteration. What remains after all pairing is 2, the missing index.

Common Mistakes

1. Integer overflow in the Gauss formula

Forgetting to cast before multiplying in statically typed languages.

// Wrong in Java — overflows for large n
int expected = n * (n + 1) / 2;

// Correct
long expected = (long) n * (n + 1) / 2;

2. Wrong XOR initialization

Starting result = 0 and forgetting to include n itself in the XOR loop.

# Wrong — misses index n entirely
result = 0
for i, num in enumerate(nums):
    result ^= i ^ num

# Correct — either initialize to n, or loop range(n+1) separately
result = n
for i, num in enumerate(nums):
    result ^= i ^ num

The array has n elements at indices 0..n-1, but the full range is 0..n. The value n must enter the XOR somewhere. Initializing result = n is the cleanest way.

3. Off-by-one in the range

The range is [0, n] inclusive, meaning n + 1 total values. A common mistake is treating it as [1, n] and computing n*(n+1)/2 - n/2 or iterating range(n) instead of range(n+1).

# Wrong — checks [0, n-1], misses n
for i in range(len(nums)):
    if i not in s:
        return i

# Correct — checks [0, n]
for i in range(len(nums) + 1):
    if i not in s:
        return i

Solutions

Python

from typing import List

class Solution:

    # Approach 1: Sort — O(n log n) time, O(1) space
    def missingNumber_sort(self, nums: List[int]) -> int:
        nums.sort()
        for i, num in enumerate(nums):
            if num != i:
                return i
        return len(nums)  # n itself is missing

    # Approach 2: HashSet — O(n) time, O(n) space
    def missingNumber_set(self, nums: List[int]) -> int:
        seen = set(nums)
        for i in range(len(nums) + 1):
            if i not in seen:
                return i

    # Approach 3: Gauss Formula — O(n) time, O(1) space
    def missingNumber_gauss(self, nums: List[int]) -> int:
        n = len(nums)
        expected = n * (n + 1) // 2  # Python handles big integers natively
        return expected - sum(nums)

    # Approach 4: XOR — O(n) time, O(1) space, no overflow risk
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)          # start with n (index that has no value pair)
        for i, num in enumerate(nums):
            result ^= i ^ num       # cancel paired index and value
        return result               # only the missing index remains

JavaScript

// Approach 1: Sort — O(n log n) time, O(1) space
function missingNumber_sort(nums) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i) return i;
    }
    return nums.length; // n itself is missing
}

// Approach 2: HashSet — O(n) time, O(n) space
function missingNumber_set(nums) {
    const seen = new Set(nums);
    for (let i = 0; i <= nums.length; i++) {
        if (!seen.has(i)) return i;
    }
}

// Approach 3: Gauss Formula — O(n) time, O(1) space
function missingNumber_gauss(nums) {
    const n = nums.length;
    const expected = (n * (n + 1)) / 2; // safe in JS up to 2^53
    return expected - nums.reduce((sum, x) => sum + x, 0);
}

// Approach 4: XOR — O(n) time, O(1) space, no overflow risk
function missingNumber(nums) {
    let result = nums.length; // start with n
    for (let i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i]; // cancel paired index and value
    }
    return result; // only the missing index survives
}

Complexity Analysis

Trade-off summary: Gauss and XOR are tied on time and space. XOR wins on robustness and elegance. Gauss wins on immediate readability for someone unfamiliar with bit manipulation. In an interview, present both and explain the overflow distinction — that is what separates good answers from great ones.

Follow-up Questions

Interviewers rarely stop at 268. The following problems are direct extensions of the same underlying insight:

LC 287 — Find the Duplicate Number

Given an array of n+1 integers where values are in [1, n], find the duplicate. The XOR approach from 268 does not directly apply because numbers can repeat more than once. The elegant solution here is Floyd's cycle detection (tortoise and hare), treating the array as a linked list where nums[i] points to index nums[i]. One duplicate creates a cycle.

LC 448 — Find All Numbers Disappeared in an Array

Given n integers in [1, n] (some appear twice, some zero times), find all missing values. The key insight: use the array itself as a hash map by negating values at indices corresponding to seen numbers. Any index still positive at the end holds a missing value. O(n) time, O(1) extra space.

LC 41 — First Missing Positive

The hardest of the group (Hard difficulty). Given an unsorted array, find the smallest missing positive integer. The classic technique is cyclic sort: place each number x at index x - 1 if it is in range [1, n], then scan for the first index where nums[i] != i + 1. O(n) time, O(1) space.

The thread connecting all three: the array's indices encode information about which values have been seen. Recognizing that indices and values are in the same range unlocks O(1) space solutions across the entire family.

This Pattern Solves

Problems where you need to identify a missing or extra element in a bounded integer range can often be solved with one of:

• Gauss / prefix-sum trick — when the range is [0, n] or [1, n] and arithmetic is safe
• XOR pairing — when you need overflow immunity or the constraint explicitly forbids math
• In-place marking — when multiple elements are missing or duplicated (negate values at seen indices)
• Cyclic sort — when the range is [1, n] and you want to physically place elements at their correct indices

Recognizing which technique applies and why is more valuable to an interviewer than any individual solution.

Key Takeaway

Missing Number is a litmus test for how deeply you understand algorithm trade-offs. The four valid approaches — Sort, HashSet, Gauss, XOR — each exist because different constraints rule out the others. XOR is the final answer not because it is the simplest to code, but because it is immune to overflow, requires no arithmetic, and reveals a deep insight about algebraic cancellation that scales to much harder problems. When an interviewer peels away constraints one by one, the goal is to watch whether you are navigating the space of options or just reciting a memorized solution.