Missing Number

1. Problem & Core Objective

Given an array containing n distinct numbers drawn from [0, n], return the one number in that range which is missing.

[3,0,1]        →  2       (n = 3, range is 0..3)
[0,1]          →  2       (n = 2, range is 0..2 — the missing one is at the END)
[9,6,4,2,3,5,7,0,1]  →  8

Constraints: 1 <= n <= 10^4, all numbers distinct and in [0, n]. The follow-up asks for O(n) time and O(1) extra space.

What's actually being tested: recognising that the array and the range [0, n] are two multisets differing by exactly one element, and that any operation with an inverse can extract that difference. Two such operations are available — XOR and addition — and knowing why you'd pick one over the other is the real question.

2. First-Principles Thought Process

Frame it as a difference of two collections

The array holds n values. The complete range 0..n holds n + 1. They agree on everything except the missing number. So:

Combine the array and the range with an operation under which matched pairs cancel, and the survivor is the answer.

Two operations qualify:

Both are one pass and constant space. This is the same structure as Single Number, with the second copy of each value supplied by the range rather than by the array.

The XOR version, and why it's a single loop

int result = nums.length;                        // seed with n, the one index the loop can't reach
for (int i = 0; i < nums.length; i++)
    result ^= i ^ nums[i];

Each i from 0 to n−1 is XORed in as an index, and each array value is XORed in as a value. Every number that appears in both collections cancels. The value n never appears as an index — the loop stops at n−1 — so it's seeded before the loop.

If the answer is n itself, the seed survives untouched; if not, the seed is cancelled by whichever array element equals n. Either way the algebra handles it without a branch.

The Gauss version, and exactly where it breaks

int expected = n * (n + 1) / 2;
for (int v : nums) expected -= v;
return expected;

n(n+1)/2 overflows int once n is large enough. Measured: the first n for which n(n+1)/2 exceeds Integer.MAX_VALUE is 65,536 — the true value is 2,147,516,416 against a maximum of 2,147,483,647, and the int computation yields 32,768 instead.

At the stated constraint of n <= 10^4 the sum peaks at about 5×10^7, so it is safe here. But the safety is a fact about the constraints, not the algorithm — which is precisely the sentence worth saying out loud.

Subtracting as you go (expected -= v inside the loop) rather than summing first also helps: the running value stays near the answer instead of climbing to the full triangular number. That's a genuine mitigation, not a stylistic choice.

Why XOR is the better default

XOR produces no carries, so it cannot overflow at any width, for any input. The correctness argument doesn't reference the constraints at all. That's the reason to reach for it even though both solutions are O(n)/O(1) here.

3. Solution Paths

Approach 1 — Brute force: sort

public int missingNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) if (nums[i] != i) return i;
    return nums.length;
}

• Time O(n log n) · Space O(1) (in-place primitive sort)

Counter-questions on this approach

⭐ "Why the return nums.length after the loop?"

Because if every position matches its index, the array is exactly 0..n−1 and the missing value is n. That's the [0,1] case, where the answer is 2.

It's easy to miss, and the failure is a wrong answer rather than an exception — the loop simply falls through.

"It meets the space bound. What's wrong with it?"

The follow-up asks for linear time. And it mutates the caller's array, which is a real side effect I'd want to flag — nums.clone() first if that matters.

"Is Arrays.sort on int[] really O(1) space?"

Effectively. It's dual-pivot quicksort, in-place apart from O(log n) recursion. The Integer[] overload uses TimSort, which allocates O(n) — a distinction worth knowing (04).

Approach 2 — Hash set

public int missingNumber(int[] nums) {
    Set<Integer> present = new HashSet<>();
    for (int v : nums) present.add(v);
    for (int i = 0; i <= nums.length; i++) if (!present.contains(i)) return i;
    return -1;                                      // unreachable
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why does the second loop go to <= nums.length?"

Because the candidate range is [0, n] inclusive — n + 1 values for an array of length n. Stopping at < nums.length silently misses the case where n itself is the answer.

Same off-by-one as the sorted version's fall-through, in a different disguise. It's the defining edge case of this problem.

"Could a boolean[] replace the set?"

Yes: boolean[n+1], mark, then scan. Still O(n) space but with a ~50× smaller constant than a HashSet<Integer>, and no boxing. If O(n) space were acceptable this is the version I'd write.

It doesn't meet the follow-up either, but it's a much better O(n).

Approach 3 — Gauss summation

public int missingNumber(int[] nums) {
    int n = nums.length;
    int result = n * (n + 1) / 2;
    for (int v : nums) result -= v;
    return result;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Where does this overflow, exactly?"

n(n+1)/2 exceeds Integer.MAX_VALUE first at n = 65,536: the true value is 2,147,516,416 against a limit of 2,147,483,647, and the int expression evaluates to 32,768 — a small positive number, so there's no exception and no obvious symptom.

At n <= 10^4 the peak is about 5×10^7, well inside range. But I'd say explicitly that the safety comes from the constraint, not the code.

"How would you make it safe?"

Three options, in increasing order of what they buy:

1. Subtract inside the loop (as written) rather than summing everything first — the accumulator stays near the answer instead of reaching the full triangular number.
2. Use long for the sum and narrow at the end.
3. Use XOR, which has no overflow mode at all.

The third is why I'd pick XOR for an unfamiliar constraint set.

"Does the subtract-as-you-go trick fully fix it?"

No. n * (n + 1) / 2 is computed before the loop starts, so it overflows before any subtraction happens. The trick protects the running value, not the initial one.

A fully safe integer version interleaves: for (int i = 0; i < n; i++) result += i - nums[i]; then result += n. Every partial sum stays bounded by n.

"What if the values could be negative or out of range?"

Both arithmetic versions break — the sum identity assumes the multiset is exactly 0..n minus one element. XOR breaks too, for the same reason. This is a precondition, not a robustness property.

Approach 4 — XOR (optimal)

public int missingNumber(int[] nums) {
    int result = nums.length;                       // the index the loop never reaches
    for (int i = 0; i < nums.length; i++)
        result ^= i ^ nums[i];
    return result;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Walk through why this works."

The full expression is n ^ (0 ^ 1 ^ … ^ (n−1)) ^ (nums[0] ^ … ^ nums[n−1]), which is the XOR of every element of 0..n together with every element of the array.

Each number present in both collections appears exactly twice and cancels by x ^ x = 0. The missing number appears only once — from the range side — so it survives. And x ^ 0 = x clears away all the cancelled pairs.

⭐ "Why seed with nums.length?"

Because the loop supplies indices 0 through n−1, so the value n is never contributed as an index even though it's part of the candidate range. Seeding with it completes the range.

It also handles the tricky case for free: if n is the answer, nothing cancels it; if it isn't, some array element equals n and cancels it. No branch either way.

"Could you seed with 0 and loop i to n instead?"

Yes — for (int i = 0; i <= n; i++) result ^= i; then a second loop over the values. That's two passes and clearer to some readers. The single-loop form is the same computation with the ranges interleaved.

Both are correct; I'd write whichever I could explain faster under pressure.

"Can this overflow or misbehave on any input in range?"

No. XOR produces no carries, so the result is always a valid int regardless of magnitude. That's the whole argument for preferring it over Gauss here.

"What if the array were empty?"

n = 0, the loop never runs, and the seed 0 is returned — correct, since the range [0, 0] minus an empty array leaves 0. The constraints say n >= 1, but it's nice that the degenerate case falls out.

4. Why the Optimal Solution Wins

Both linear versions are optimal; every element must be read and one word of state suffices.

Write the XOR version, and mention Gauss as the arithmetic alternative with the overflow threshold. Naming the exact n at which the sum breaks is more convincing than a vague "it might overflow" — and it's the kind of detail that shows you checked.

5. Java Prerequisites

Range and length arithmetic

int n = nums.length;        // the array holds n values...
// ...drawn from [0, n], which has n + 1 candidates

The whole problem is that off-by-one. Writing the comment is not a formality.

XOR seeded outside the loop

int result = nums.length;
for (int i = 0; i < nums.length; i++) result ^= i ^ nums[i];

Triangular number and its range

int s = n * (n + 1) / 2;        // overflows int at n = 65,536
long s = (long) n * (n + 1) / 2;  // cast BEFORE multiplying, not after

(long) (n * (n + 1) / 2) is a common non-fix — the multiplication already happened in int before the cast.

Arrays.sort mutates

Arrays.sort(nums);              // reorders the caller's array
Arrays.sort(nums.clone());      // sorts a copy — and discards it, so bind it

boolean[] beats HashSet<Integer> for dense small keys

boolean[] present = new boolean[n + 1];     // 1 byte each, no boxing

6. Interview Communication Guide

Clarifying questions: Is the range [0, n] inclusive, so there are n + 1 candidates for n array slots (yes — that's where the off-by-one lives)? Are values guaranteed distinct and in range (yes; both my solutions depend on it)? Is exactly one missing (yes)? Are the O(n) time and O(1) space targets firm (they rule out sorting and a hash set)?

The pitch

"The array and the range 0..n are two collections that differ by exactly one element. So I want an operation under which matched pairs cancel, leaving the odd one out.

XOR does that: x ^ x = 0, x ^ 0 = x, and it's associative and commutative so the array needn't be sorted. XOR everything in the array together with everything in 0..n, and every number present in both cancels — only the missing one survives.

In one loop: seed the result with n, then result ^= i ^ nums[i] for i from 0 to n−1. The seed is there because the loop's indices only reach n−1, so n never enters as an index. And it handles the awkward case with no branch — if n is the answer nothing cancels it, and if it isn't, some array element equals n and does.

The arithmetic alternative is n(n+1)/2 − sum(nums), same complexity. I'd mention it and then say why I didn't write it: that expression overflows int starting at n = 65,536, where the true value is 2,147,516,416 and the int computation quietly returns 32,768. At the stated limit of 10^4 it's safe, but that's a property of the constraints rather than of the code. XOR has no overflow mode at any width.

The edge case I'd name before running anything is [0,1], where the answer is 2 — the missing number is at the top of the range, not inside the array's span. Every wrong version of this problem gets that one wrong, whether it's a loop bound of < n instead of <= n or a forgotten fall-through return."

Edge cases to volunteer:

Name [0,1] and [1] together. One puts the answer at the top of the range and the other at the bottom; between them they catch every off-by-one and every bad accumulator seed this problem admits.

7. Follow-Up Questions — Modified Constraints

⭐ "Two numbers are missing instead of one."

XOR everything to get a ^ b. That's non-zero, so some bit differs — isolate the lowest with x & -x, partition both the array and the range on that bit, and XOR each side independently. a and b land in different partitions and everything else cancels within its partition.

O(n) time, O(1) space. Same technique as Single Number's two-singleton follow-up, and the Gauss approach can't be extended this cleanly — you'd get a + b and need a second equation such as a² + b².

⭐ "Find the duplicate instead — n + 1 values in [1, n] with one repeated."

XOR doesn't work, because the array isn't a permutation-minus-one. The standard answer is Floyd's cycle detection on the functional graph i → nums[i]: O(n) time, O(1) space, and the input is never modified.

That's LeetCode 287, and it's worth naming the difference: "exactly one missing" is an XOR problem, "exactly one duplicate" is a cycle problem.

"What if the array were sorted?"

Binary search: the missing number is the first index i where nums[i] != i. O(log n), which beats every linear solution. Sortedness is more information than XOR can exploit.

"What if you couldn't read the array twice, and it arrived as a stream?"

XOR is already single-pass with one word of state, so it handles a stream natively — as does Gauss. The sorting and hash-set versions do not. That's a practical advantage worth stating.

"What if n were 10^9?"

XOR is unchanged. Gauss would need long, since n(n+1)/2 is about 5×10^17 — comfortably inside long but nowhere near int. The threshold I measured, n = 65,536, is the exact point where that decision starts to matter.

"Could you find the missing number without XOR or arithmetic?"

Cycle sort: repeatedly swap nums[i] to index nums[i] until each value sits at its own index, then scan for the mismatch. O(n) time, O(1) space — but it mutates the input, which the other solutions don't.

It's the right tool when the question is "find all missing numbers in [1, n]" (LeetCode 448), where no single accumulator can hold the answer.

"How would you verify a solution to this?"

Differential testing against three independent implementations — sort, hash set and Gauss — on randomized permutations with the missing value deliberately placed at 0, at n, and in between. That's what I did here: 20,000 cases across all four approaches, agreeing everywhere.