Missing Number

Missing Number

What is this problem about?

The Missing Number problem gives you an array containing n distinct numbers from the range [0, n]. Exactly one number is missing. Find it. This Missing Number coding problem is one of the most versatile easy-level questions, solvable with five different techniques: math (Gauss sum), XOR, hash table, sorting, or binary search. Mastering all approaches makes it an excellent teaching problem.

Why is this asked in interviews?

This problem is asked by Apple, Microsoft, Google, Amazon, Meta, Goldman Sachs, Bloomberg, Adobe, and nearly every major tech company. It's used as a screening question and as a discussion starter for multiple algorithmic approaches. Interviewers love asking candidates to list all possible solutions and explain trade-offs. The array, math, hash table, sorting, binary search, and bit manipulation interview pattern are all represented.

Algorithmic pattern used

Multiple approaches:

• Math: Expected sum = n*(n+1)/2. Subtract the actual array sum. Result is the missing number.
• XOR: XOR all indices 0..n with all array values. Duplicate values cancel out, leaving the missing number.
• Hash set: Insert all values, then check which 0..n is absent.
• Binary search: Sort array, check if arr[i] != i.

Example explanation

Array: [3, 0, 1]. n=3. Expected sum = 3*4/2 = 6. Actual sum = 4. Missing = 6-4 = 2.

XOR approach: 0^1^2^3 ^ 3^0^1 = 2. (All matching pairs cancel, leaving 2.)

Common mistakes candidates make

• Integer overflow on large n when computing the Gauss sum (use long).
• Forgetting that the array contains values [0..n], not [1..n].
• XOR approach: indexing errors when XOR-ing indices vs values.
• Not recognizing the O(1) space math and XOR solutions.

Interview preparation tip

Always know at least two approaches for Missing Number: the math formula (O(1) space) and the XOR trick. Being able to explain why XOR works — duplicate values cancel because x ^ x = 0 and x ^ 0 = x — shows deep bit manipulation understanding. This problem is commonly extended: "find two missing numbers," "find the duplicate and missing number," etc. Practice all variants to prepare for follow-up questions.