Loading…

easyBit ManipulationLC #268Frequently asked

Missing Number

Q: How do you solve Missing Number using the Gauss Sum — Expected Minus Actual approach?

When to use it: A great first O(1)-space answer. 'The sum of 0..n is known by Gauss's formula; subtract the actual sum and the difference is the missing number.' Compute the sum the array *would* have if nothing were missing — `0 + 1 + … + n = n(n+1)/2` — and subtract the array's actual sum. The shortfall is exactly the missing number. **Why the difference is the answer.** The full range `[0, n]` sums to `n(n+1)/2` (Gauss's formula). The array contains every one of those values except one, so its sum is the full sum minus the missing value. Rearranging: `missing = expected − actual`. It's pure conservation of total. **Why this is elegant but fragile.** It's O(1) space and a clean one-liner of intent, but `n(n+1)/2` and the running sum can both exceed the integer range for large `n`. In Java with `int`, `n ≈ 10⁵` is safe, but a larger constraint or a 32-bit accumulator could silently overflow and return garbage. That fragility is exactly what the XOR approach removes — and naming the risk out loud is what separates a strong candidate. **A subtraction-as-you-go variant.** You can fold expected and actual into a single accumulator: start at `n`, then for each index `i` add `i` and subtract `nums[i]`. This keeps the running value small and reduces overflow risk, though XOR is still the cleanest overflow-proof option. Time complexity: O(n). Space complexity: O(1).

Q: How do you solve Missing Number using the XOR Indices With Values (Optimal) approach?

When to use it: The overflow-proof answer to prefer. 'XOR every index 0..n with every value; matching pairs cancel and the missing number survives.' XOR together two things: every index in `0..n` and every value in the array. Because the values are a subset of `0..n` missing exactly one element, each present value cancels against the identical index, and the lone index with no matching value survives — that's the missing number. **Why pairing index with value cancels.** Think of XOR-ing the multiset `{0,1,…,n} ∪ {all nums}`. Every number that *is* present appears twice — once as an index, once as a value — and `a ^ a = 0` annihilates each such pair. The missing number appears only once (as an index `0..n`, never as a value), so it alone is left standing. **Why we seed with `n`.** The loop variable `i` only reaches `n − 1` (array length is `n`), but the range of possible answers is `0..n` inclusive. Seeding the accumulator with `n` injects that final index so the full index set `0..n` is represented. A common bug is forgetting this seed, which fails whenever the answer is `n` itself. **Why XOR beats the sum.** XOR never overflows — it's a fixed set of bit operations with no carry growth. The sum approach can exceed the integer range for large `n`; XOR cannot. Same O(n) time and O(1) space, strictly safer. That's why, when an interviewer asks 'what if n is huge?', XOR is the clean reply. Time complexity: O(n). Space complexity: O(1).

LCPractice

Bit Manipulation · 5 of 20 · 6 min

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

Follow-up: could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

In plain English

There are n slots holding n distinct values drawn from the n + 1 possible values 0 through n. Exactly one value from that range never appears. The hash-set answer is trivial; the interesting part is the O(1)-space requirement and the overflow trap in the arithmetic approach.

Examples

Example 1

Input: nums = [3, 0, 1]
Output: 2
Note: n = 3, range is [0, 3]. Present: 0, 1, 3. Missing: 2.

Example 2

Input: nums = [0, 1]
Output: 2
Note: n = 2, range [0, 2]. Present: 0, 1. The missing value is the top endpoint, 2.

Example 3

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Note: n = 9, range [0, 9]. Every value present except 8.

Constraints

n == nums.length
0 ≤ nums[i] ≤ n
All the numbers of nums are unique
Follow-up target: O(n) time, O(1) extra space

Clarifying questions4First question: Is the range exactly [0, n] with n = array length?Explore questions

Q1.Is the range exactly [0, n] with n = array length?
Yes. There are n numbers occupying n of the n + 1 slots in [0, n], so exactly one is missing.
Q2.Are all numbers distinct?
Yes. That guarantee is what makes both the sum difference and the XOR pairing work cleanly.
Q3.Could the missing number be 0 or n itself?
Yes — the missing value can be either endpoint. The XOR seed of n and the inclusion of index 0 both handle the endpoints.
Q4.Is the O(1)-space, O(n)-time follow-up the target?
Yes, which rules out sorting and a hash set as the intended answer, even though both are correct.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

An array holds n distinct numbers from the range [0, n] with exactly one missing. The math answer subtracts the actual sum from the expected sum n(n+1)/2. The overflow-safe answer XORs every index 0..n together with every value: each present number cancels with its index, leaving the missing one. Both are O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can find an O(1)-space solution beyond the obvious hash set — and whether you anticipate integer overflow in the sum approach and reach for XOR to sidestep it.

Where candidates slip

Using a hash set (O(n) space), or using the sum formula but computing n*(n+1)/2 in a way that overflows for large n, or seeding the XOR loop wrong so index n is never included.

How to stand out

Offer both the sum and XOR solutions, explain that XOR is overflow-safe, and explain WHY indices-XOR-values isolates the gap (each present number cancels its own index).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Gauss Sum — Expected Minus Actual	`O(n)`	`O(1)`	A great first O(1)-space answer. 'The sum of 0..n is known by Gauss's formula; subtract the actual sum and the difference is the missing number.'	Read
2	XOR Indices With Values (Optimal)Optimal	`O(n)`	`O(1)`	The overflow-proof answer to prefer. 'XOR every index 0..n with every value; matching pairs cancel and the missing number survives.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewOne number missing from [0, n]O(1) space required?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Gauss Sum — Expected Minus Actual

TimeO(n)SpaceO(1)

A great first O(1)-space answer. 'The sum of 0..n is known by Gauss's formula; subtract the actual sum and the difference is the missing number.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If no number were missing, you'd know the exact total of 0 + 1 + ... + n. What's a closed form for that total?

2Hint 2Explore hint

The sum of 0..n is n(n+1)/2. The array's actual sum is short by exactly the missing value.

3Hint 3Explore hint

Compute expected = n(n+1)/2, subtract the sum of nums, and the remainder is the missing number.

A · Core idea

Compute the sum the array would have if nothing were missing — 0 + 1 + … + n = n(n+1)/2 — and subtract the array's actual sum. The shortfall is exactly the missing number.

Why the difference is the answer. The full range [0, n] sums to n(n+1)/2 (Gauss's formula). The array contains every one of those values except one, so its sum is the full sum minus the missing value. Rearranging: missing = expected − actual. It's pure conservation of total.

Why this is elegant but fragile. It's O(1) space and a clean one-liner of intent, but n(n+1)/2 and the running sum can both exceed the integer range for large n. In Java with int, n ≈ 10⁵ is safe, but a larger constraint or a 32-bit accumulator could silently overflow and return garbage. That fragility is exactly what the XOR approach removes — and naming the risk out loud is what separates a strong candidate.

A subtraction-as-you-go variant. You can fold expected and actual into a single accumulator: start at n, then for each index i add i and subtract nums[i]. This keeps the running value small and reduces overflow risk, though XOR is still the cleanest overflow-proof option.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 0, 1]

expected

n(n+1)/2 = 3·4/2

Stateexpected = 6

Final result2

C · Code with teaching comments

Reference implementation previewpublic int missingNumber(int[] nums) { int n = nums.length; int expected = n * (n + 1) / 2; int actual = 0; for (int x : nums) {Explore the full code

solution.javaJava

Gauss Sum — Expected Minus Actual — reference

3 teaching notes

1
public int missingNumber(int[] nums) {
2
    int n = nums.length;
3
    // Gauss's formula for 0 + 1 + ... + n. Watch for overflow when n is large.
4
    int expected = n * (n + 1) / 2;
5
    int actual = 0;
6
    for (int x : nums) {
7
        // Sum of the values actually present — short by the missing one.
8
        actual += x;
9
    }
10
    // The deficit equals the single missing value.
11
    return expected - actual;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is a conservation argument: the total of a complete set is fixed, so any single omission shows up as an exact, computable deficit. The same 'expected total minus observed total' lever solves 'find the duplicate by sum' and 'find the corrupted entry' style problems.

ComplexityO(n) time, O(1) space — One pass to sum the array is O(n); the expected sum is a constant-time formula. Only a couple of accumulators → O(1) space.

E · Edge cases and pitfalls5nums = [0] — n = 1, expected = 1, actual = 0 → missing = 1 (the top endpoint).Explore edge cases

Edge cases handled

nums = [0]n = 1, expected = 1, actual = 0 → missing = 1 (the top endpoint).
nums = [1]n = 1, expected = 1, actual = 1 → missing = 0 (the bottom endpoint).

Pitfalls

Integer overflow on n*(n+1)/2 or the running sum for large n in fixed-width types.
Using n = nums.length but indexing the range as [0, n-1] instead of [0, n] — off by one.
Computing n*(n+1) before dividing in a narrow type, doubling the overflow risk.

03.2

Approach 2 of 2 · Optimal

XOR Indices With Values (Optimal)

TimeO(n)SpaceO(1)

The overflow-proof answer to prefer. 'XOR every index 0..n with every value; matching pairs cancel and the missing number survives.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recall a ^ a = 0. If you XOR a complete set of numbers against the array's values, what cancels and what survives?

2Hint 2Explore hint

XOR together all indices 0..n AND all array values. Every present value v has a matching index equal to v, so they pair up and vanish.

3Hint 3Explore hint

Seed the accumulator with n (since indices in the loop only go to n-1), then XOR in both i and nums[i] each step.

A · Core idea

XOR together two things: every index in 0..n and every value in the array. Because the values are a subset of 0..n missing exactly one element, each present value cancels against the identical index, and the lone index with no matching value survives — that's the missing number.

Why pairing index with value cancels. Think of XOR-ing the multiset {0,1,…,n} ∪ {all nums}. Every number that is present appears twice — once as an index, once as a value — and a ^ a = 0 annihilates each such pair. The missing number appears only once (as an index 0..n, never as a value), so it alone is left standing.

Why we seed with `n`. The loop variable i only reaches n − 1 (array length is n), but the range of possible answers is 0..n inclusive. Seeding the accumulator with n injects that final index so the full index set 0..n is represented. A common bug is forgetting this seed, which fails whenever the answer is n itself.

Why XOR beats the sum. XOR never overflows — it's a fixed set of bit operations with no carry growth. The sum approach can exceed the integer range for large n; XOR cannot. Same O(n) time and O(1) space, strictly safer. That's why, when an interviewer asks 'what if n is huge?', XOR is the clean reply.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 0, 1]

Array state

seed

acc = 3 (the index n)

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

XOR Indices With Values (Optimal) — optimal

3 teaching notes

1
public int missingNumber(int[] nums) {
2
    // Seed with n so index n is included — the loop only reaches n-1.
3
    int missing = nums.length;
4
    for (int i = 0; i < nums.length; i++) {
5
        // Fold in both the index and the value; present numbers cancel their own index.
6
        missing ^= i ^ nums[i];
7
    }
8
    // The one index with no matching value is the missing number.
9
    return missing;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

This is the Single Number trick generalised: instead of pairing duplicate values, you pair indices with values. Any time you have a complete labelled set with one element absent (or duplicated), XOR of labels against contents isolates the anomaly in O(1) space without arithmetic overflow.

ComplexityO(n) time, O(1) space — One pass doing two constant-time XORs per element is O(n); a single accumulator is O(1) space. No multiplication means no overflow.

E · Edge cases and pitfalls5nums = [0] — Seed 1, then ^= 0 ^ 0 = 0 → result 1. Missing top endpoint handled by the n seed.Explore edge cases

Edge cases handled

nums = [0]Seed 1, then ^= 0 ^ 0 = 0 → result 1. Missing top endpoint handled by the n seed.
nums = [1]Seed 1, then ^= 0 ^ 1 → 1 ^ 0 ^ 1 = 0 → result 0. Missing bottom endpoint.

Pitfalls

Forgetting to seed with n — fails whenever the missing number is n itself.
XOR-ing only the values or only the indices instead of both — you must pair them.
Treating this like Single Number and pairing values with values — here it's indices against values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int missingNumber(int[] nums) { int missing = nums.length; for (int i = 0; i < nums.length; i++) { missing ^= i ^ nums[i]; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the XOR seed of n

The loop index only reaches n - 1, so the value n is never XOR-ed in. If the missing number is n, the result is wrong unless you seed the accumulator with n.

Explore the code comparison

Don't write this

int missing = 0;            // should start at n
for (int i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
}
return missing;             // fails when answer is n

Write this instead

int missing = nums.length;  // seed with n covers the full range
for (int i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
}
return missing;

Overflow in the sum approach

n*(n+1) can exceed Integer.MAX_VALUE before the divide, producing a wrong expected sum. Use a long, fold subtraction into the loop, or prefer XOR.

Explore the code comparison

Don't write this

int expected = n * (n + 1) / 2;   // n*(n+1) overflows int for large n

Write this instead

long expected = (long) n * (n + 1) / 2;   // promote to long before multiplying

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Index–value pairing (XOR cancellation / sum difference)

Code pattern to memorize

missing = n
for i, x in enumerate(nums):
    missing ^= i ^ x   # indices 0..n-1 XOR all values, seed n
return missing

Rules to remember

1Seed the XOR with n so the full index set 0..n is covered (the loop only reaches index n-1).
2Every value that IS present cancels with its matching index via a ^ a = 0; the missing number has no value to cancel its index.
3The sum formula n(n+1)/2 − Σnums is the same idea arithmetically, but can overflow for large n; XOR never overflows.
4Both run in O(n) time and O(1) space — no sorting, no hash set needed.
5Don't confuse this with Single Number: here you pair indices with values, not values with their duplicates.

Use this pattern when

Find the one missing element from a contiguous range [0, n]
Numbers are distinct and span a known complete range minus one
You want O(1) space and want to avoid overflow → XOR variant
A 'one element absent from 1..n' framing of any kind

Choose another pattern when

Multiple numbers missing → XOR/sum collapse them together; use a boolean array or set
Range has duplicates → the pairing logic breaks (that's Find the Duplicate)
Numbers aren't a contiguous range → no expected sum/index structure to exploit
You also need WHICH indices are present, not just the gap → use a presence array

Interview takeaway

Missing Number is two clean O(1)-space tricks wearing one prompt: Gauss's sum minus the actual sum, or XOR of indices against values. The XOR version is the one to prefer aloud — it's immune to integer overflow, which is the exact gotcha interviewers probe on the sum approach.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternIndex–value pairing for the odd one out. Recognise it when a contiguous range [0, n] is missing exactly one element. XOR (overflow-safe) or expected-minus-actual sum both isolate the gap in O(1) space — the same conservation idea behind Single Number.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Single Number
The pure XOR-cancellation parent: pair duplicate values instead of indices with values.
Find All Numbers Disappeared in an Array
Coming soon
Multiple missing numbers — XOR/sum collapse them, so mark presence in-place by negating indices.
Find the Duplicate Number
Coming soon
Range with a duplicate instead of a gap — Floyd's cycle detection on the value-as-pointer graph.
First Missing Positive
Coming soon
Find the smallest missing positive — index-as-hash placement, O(1) space, harder cousin.

Same pattern

←

Reverse Bits

Continue · Next problem

Sum of Two Integers

easyBit ManipulationLC #268Frequently asked

Missing Number

LCPractice

Bit Manipulation · 5 of 20 · 6 min

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

Follow-up: could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

In plain English

Examples

Example 1

Input: nums = [3, 0, 1]
Output: 2
Note: n = 3, range is [0, 3]. Present: 0, 1, 3. Missing: 2.

Example 2

Input: nums = [0, 1]
Output: 2
Note: n = 2, range [0, 2]. Present: 0, 1. The missing value is the top endpoint, 2.

Example 3

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Note: n = 9, range [0, 9]. Every value present except 8.

Constraints

n == nums.length
0 ≤ nums[i] ≤ n
All the numbers of nums are unique
Follow-up target: O(n) time, O(1) extra space

Clarifying questions4First question: Is the range exactly [0, n] with n = array length?Explore questions

Q1.Is the range exactly [0, n] with n = array length?
Yes. There are n numbers occupying n of the n + 1 slots in [0, n], so exactly one is missing.
Q2.Are all numbers distinct?
Yes. That guarantee is what makes both the sum difference and the XOR pairing work cleanly.
Q3.Could the missing number be 0 or n itself?
Yes — the missing value can be either endpoint. The XOR seed of n and the inclusion of index 0 both handle the endpoints.
Q4.Is the O(1)-space, O(n)-time follow-up the target?
Yes, which rules out sorting and a hash set as the intended answer, even though both are correct.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can find an O(1)-space solution beyond the obvious hash set — and whether you anticipate integer overflow in the sum approach and reach for XOR to sidestep it.

Where candidates slip

Using a hash set (O(n) space), or using the sum formula but computing n*(n+1)/2 in a way that overflows for large n, or seeding the XOR loop wrong so index n is never included.

How to stand out

Offer both the sum and XOR solutions, explain that XOR is overflow-safe, and explain WHY indices-XOR-values isolates the gap (each present number cancels its own index).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Gauss Sum — Expected Minus Actual	`O(n)`	`O(1)`	A great first O(1)-space answer. 'The sum of 0..n is known by Gauss's formula; subtract the actual sum and the difference is the missing number.'	Read
2	XOR Indices With Values (Optimal)Optimal	`O(n)`	`O(1)`	The overflow-proof answer to prefer. 'XOR every index 0..n with every value; matching pairs cancel and the missing number survives.'	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Gauss Sum — Expected Minus Actual

TimeO(n)SpaceO(1)

A great first O(1)-space answer. 'The sum of 0..n is known by Gauss's formula; subtract the actual sum and the difference is the missing number.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If no number were missing, you'd know the exact total of 0 + 1 + ... + n. What's a closed form for that total?

2Hint 2Explore hint

The sum of 0..n is n(n+1)/2. The array's actual sum is short by exactly the missing value.

3Hint 3Explore hint

Compute expected = n(n+1)/2, subtract the sum of nums, and the remainder is the missing number.

A · Core idea

Compute the sum the array would have if nothing were missing — 0 + 1 + … + n = n(n+1)/2 — and subtract the array's actual sum. The shortfall is exactly the missing number.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 0, 1]

expected

n(n+1)/2 = 3·4/2

Stateexpected = 6

Final result2

C · Code with teaching comments

Reference implementation previewpublic int missingNumber(int[] nums) { int n = nums.length; int expected = n * (n + 1) / 2; int actual = 0; for (int x : nums) {Explore the full code

solution.javaJava

Gauss Sum — Expected Minus Actual — reference

3 teaching notes

1
public int missingNumber(int[] nums) {
2
    int n = nums.length;
3
    // Gauss's formula for 0 + 1 + ... + n. Watch for overflow when n is large.
4
    int expected = n * (n + 1) / 2;
5
    int actual = 0;
6
    for (int x : nums) {
7
        // Sum of the values actually present — short by the missing one.
8
        actual += x;
9
    }
10
    // The deficit equals the single missing value.
11
    return expected - actual;
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass to sum the array is O(n); the expected sum is a constant-time formula. Only a couple of accumulators → O(1) space.

E · Edge cases and pitfalls5nums = [0] — n = 1, expected = 1, actual = 0 → missing = 1 (the top endpoint).Explore edge cases

Edge cases handled

nums = [0]n = 1, expected = 1, actual = 0 → missing = 1 (the top endpoint).
nums = [1]n = 1, expected = 1, actual = 1 → missing = 0 (the bottom endpoint).

Pitfalls

Integer overflow on n*(n+1)/2 or the running sum for large n in fixed-width types.
Using n = nums.length but indexing the range as [0, n-1] instead of [0, n] — off by one.
Computing n*(n+1) before dividing in a narrow type, doubling the overflow risk.

03.2

Approach 2 of 2 · Optimal

XOR Indices With Values (Optimal)

TimeO(n)SpaceO(1)

The overflow-proof answer to prefer. 'XOR every index 0..n with every value; matching pairs cancel and the missing number survives.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recall a ^ a = 0. If you XOR a complete set of numbers against the array's values, what cancels and what survives?

2Hint 2Explore hint

XOR together all indices 0..n AND all array values. Every present value v has a matching index equal to v, so they pair up and vanish.

3Hint 3Explore hint

Seed the accumulator with n (since indices in the loop only go to n-1), then XOR in both i and nums[i] each step.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [3, 0, 1]

Array state

seed

acc = 3 (the index n)

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

XOR Indices With Values (Optimal) — optimal

3 teaching notes

1
public int missingNumber(int[] nums) {
2
    // Seed with n so index n is included — the loop only reaches n-1.
3
    int missing = nums.length;
4
    for (int i = 0; i < nums.length; i++) {
5
        // Fold in both the index and the value; present numbers cancel their own index.
6
        missing ^= i ^ nums[i];
7
    }
8
    // The one index with no matching value is the missing number.
9
    return missing;
10
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.10 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass doing two constant-time XORs per element is O(n); a single accumulator is O(1) space. No multiplication means no overflow.

E · Edge cases and pitfalls5nums = [0] — Seed 1, then ^= 0 ^ 0 = 0 → result 1. Missing top endpoint handled by the n seed.Explore edge cases

Edge cases handled

nums = [0]Seed 1, then ^= 0 ^ 0 = 0 → result 1. Missing top endpoint handled by the n seed.
nums = [1]Seed 1, then ^= 0 ^ 1 → 1 ^ 0 ^ 1 = 0 → result 0. Missing bottom endpoint.

Pitfalls

Forgetting to seed with n — fails whenever the missing number is n itself.
XOR-ing only the values or only the indices instead of both — you must pair them.
Treating this like Single Number and pairing values with values — here it's indices against values.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int missingNumber(int[] nums) { int missing = nums.length; for (int i = 0; i < nums.length; i++) { missing ^= i ^ nums[i]; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the XOR seed of n

The loop index only reaches n - 1, so the value n is never XOR-ed in. If the missing number is n, the result is wrong unless you seed the accumulator with n.

Explore the code comparison

Don't write this

int missing = 0;            // should start at n
for (int i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
}
return missing;             // fails when answer is n

Write this instead

int missing = nums.length;  // seed with n covers the full range
for (int i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
}
return missing;

Overflow in the sum approach

n*(n+1) can exceed Integer.MAX_VALUE before the divide, producing a wrong expected sum. Use a long, fold subtraction into the loop, or prefer XOR.

Explore the code comparison

Don't write this

int expected = n * (n + 1) / 2;   // n*(n+1) overflows int for large n

Write this instead

long expected = (long) n * (n + 1) / 2;   // promote to long before multiplying

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Index–value pairing (XOR cancellation / sum difference)

Code pattern to memorize

missing = n
for i, x in enumerate(nums):
    missing ^= i ^ x   # indices 0..n-1 XOR all values, seed n
return missing

Rules to remember

1Seed the XOR with n so the full index set 0..n is covered (the loop only reaches index n-1).
2Every value that IS present cancels with its matching index via a ^ a = 0; the missing number has no value to cancel its index.
3The sum formula n(n+1)/2 − Σnums is the same idea arithmetically, but can overflow for large n; XOR never overflows.
4Both run in O(n) time and O(1) space — no sorting, no hash set needed.
5Don't confuse this with Single Number: here you pair indices with values, not values with their duplicates.

Use this pattern when

Find the one missing element from a contiguous range [0, n]
Numbers are distinct and span a known complete range minus one
You want O(1) space and want to avoid overflow → XOR variant
A 'one element absent from 1..n' framing of any kind

Choose another pattern when

Multiple numbers missing → XOR/sum collapse them together; use a boolean array or set
Range has duplicates → the pairing logic breaks (that's Find the Duplicate)
Numbers aren't a contiguous range → no expected sum/index structure to exploit
You also need WHICH indices are present, not just the gap → use a presence array

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Single Number
The pure XOR-cancellation parent: pair duplicate values instead of indices with values.
Find All Numbers Disappeared in an Array
Coming soon
Multiple missing numbers — XOR/sum collapse them, so mark presence in-place by negating indices.
Find the Duplicate Number
Coming soon
Range with a duplicate instead of a gap — Floyd's cycle detection on the value-as-pointer graph.
First Missing Positive
Coming soon
Find the smallest missing positive — index-as-hash placement, O(1) space, harder cousin.

Same pattern

←

Reverse Bits

Continue · Next problem

Sum of Two Integers