Missing Number
Asked at Google, Amazon, Microsoft, Meta
Problem
Missing Number asks you to find the single number missing from an array containing n distinct numbers taken from 0 to n. This problem has multiple elegant solutions — mathematical sum, XOR, and binary search — making it a favorite for testing whether candidates know multiple approaches.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Meta | Easy | View all Meta questions → |
How to Think About It
Math approach: the sum of 0 to n is n*(n+1)/2. Subtract the sum of the array from this expected sum. The difference is the missing number. O(n) time, O(1) space. Simple and clean.
XOR approach: XOR all numbers from 0 to n, then XOR all numbers in the array. The result is the missing number because duplicate values cancel out (a ^ a = 0). O(n) time, O(1) space. Avoids integer overflow for very large n.
Sorting approach: sort the array, then walk through looking for the first index where arr[i] != i. O(n log n) time — not optimal but works if the interviewer allows sorting.
Hash set approach: put all array elements in a set, then check 0 through n for which one is missing. O(n) time, O(n) space. Straightforward but uses extra space.
Edge cases: n = 0 (array is empty, answer is 0), n = 1 (array has one element, either 0 or 1 is missing), missing number is 0, missing number is n.
Optimal Approach
Calculate the expected sum of numbers from 0 to n using the formula n*(n+1)/2. Iterate through the array and compute the actual sum. Return expected - actual.
Walkthrough: nums = [3, 0, 1]. n = 3. Expected sum = 3*4/2 = 6. Actual sum = 3+0+1 = 4. Missing = 6-4 = 2.
Time: O(n) — one pass to sum. Space: O(1) — just two integer variables.
What Trips People Up in Real Interviews
Using sum and getting integer overflow. For very large n, n*(n+1)/2 can overflow. The XOR approach avoids this entirely. Or use long arithmetic if your language supports it.
Forgetting that the array has n elements but the range is 0 to n (n+1 possible values). This means exactly one value is missing.
Off-by-one errors in the math formula. The sum of 0 to n is n*(n+1)/2, not n*(n-1)/2.
Not considering that the array might not be sorted. The hash set and XOR approaches work regardless of order.
Solution Code
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
actual = sum(nums)
return expected - actualFrequently Asked Questions
What is the Missing Number problem?
Missing Number asks you to find the single number missing from an array containing n distinct numbers taken from 0 to n. This problem has multiple elegant solutions — mathematical sum, XOR, and binary search — making it a favorite for testing whether candidates know multiple approaches.
How do you solve Missing Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Missing Number?
Missing Number is asked at Google, Amazon, Microsoft, Meta. It is a easy difficulty problem.
What are common mistakes on Missing Number?
- Using sum and getting integer overflow. For very large n, n*(n+1)/2 can overflow. The XOR approach avoids this entirely. Or use long arithmetic if your language supports it.
- Forgetting that the array has n elements but the range is 0 to n (n+1 possible values). This means exactly one value is missing.
- Off-by-one errors in the math formula. The sum of 0 to n is n*(n+1)/2, not n*(n-1)/2.
- Not considering that the array might not be sorted. The hash set and XOR approaches work regardless of order.