EasyArrayHash TableMathBinary SearchBit ManipulationSortingUpdated Sep 2026

Missing Number

Asked at Google, Amazon, Microsoft, Meta

Difficulty

Easy

Time

O(n)

Space

O(1)

Pattern

Array

Companies

4

Problem

You get an array nums that holds n distinct integers. Every value in it comes from the range 0 to n inclusive. That range has n + 1 numbers, but the array only has n of them, so exactly one number from the range is absent.

Return that one missing number. The array is not sorted, and the numbers can appear in any order.

For example, if nums = [3,0,1], then n = 3 and the full range is {0,1,2,3}. The array contains 0, 1 and 3, so the missing value is 2.

One value is absent from the range

nums301012The given array: n = 3, so the values must come from0, 1, 2, 3.range 0..301230, 1 and 3 are in the array; 2 is the only value withno match.
The array has 3 slots but the range 0..3 has 4 values, so exactly one value never shows up.

Constraints

  • ●n == nums.length
  • ●1 <= n <= 10^4
  • ●0 <= nums[i] <= n
  • ●All the numbers of nums are unique.

Examples

Example 1
Inputnums = [3,0,1]
Output2
WhyThere are 3 numbers, so the range is 0 to 3. The array has 0, 1 and 3, which leaves 2 as the only value not present.
Example 2
Inputnums = [0,1]
Output2
WhyThere are 2 numbers, so the range is 0 to 2. Both 0 and 1 are in the array, so the absent value is 2.
Example 3
Inputnums = [9,6,4,2,3,5,7,0,1]
Output8
WhyThere are 9 numbers, so the range is 0 to 9. Every value from 0 to 9 appears except 8.

Asked At

4 companies
CompanyDifficulty
GoogleEasyView all Google questions →
AmazonEasyView all Amazon questions →
MicrosoftEasyView all Microsoft questions →
MetaEasyView all Meta questions →

How to Think About It

1

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.

2

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.

3

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.

4

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.

5

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.

Expected sum minus actual sum

n = len(nums) = 3expected = 3*4/2 = 6actual = 3+0+1 = 4return 6 - 4 = 2The formula n*(n+1)/2 gives the total of 0..n;subtracting the array total leaves the missing number.expected = n * (n + 1) / 2actual = sum(nums)answer = expected - actual
Add up the whole range with a formula, add up the array, and the gap between them is the missing value.
ComplexityTime O(n)Space O(1)One pass adds up the array, and the expected total is computed with a formula, so no extra memory is needed.

What Trips People Up in Real Interviews

1

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.

2

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.

3

Off-by-one errors in the math formula. The sum of 0 to n is n*(n+1)/2, not n*(n-1)/2.

4

Not considering that the array might not be sorted. The hash set and XOR approaches work regardless of order.

Solution Code

O(n) time
def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)
    return expected - actual

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.