Skip to main content

268. Missing Number

easy

Find the missing number in an array containing n distinct values drawn from [0, n]. Three classic solutions: hash set, arithmetic sum (Gauss), and XOR — each a one-liner once you see the trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
nums = [3,0,1]
Output
2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2

Input
nums = [0,1]
Output
2

Example 3

Input
nums = [9,6,4,2,3,5,7,0,1]
Output
8

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash set: insert every number, then loop 0..n looking for the missing one. O(n) time and space.

Hint 2

Math: the expected sum 0+1+...+n is n*(n+1)/2. Subtract the actual array sum from it. The difference is the missing number. O(n) time, O(1) space.

Hint 3

XOR: x XOR x = 0 and 0 XOR a = a. So XOR every array value with every value in [0..n]. The pair that doesn't cancel is the missing number.

Hint 4

All three are O(n) but XOR sidesteps any overflow concern with the sum formula on adversarial inputs.

Solution approach

Reveal approach

Three interview-grade approaches: (1) Gauss sum — expected = n * (n + 1) / 2, actual = sum(nums), return expected - actual. O(n) time, O(1) space. (2) XOR — start result = n. Loop i from 0 to n-1: result ^= i ^ nums[i]. Return result. Every paired (i, nums[i]) cancels out except the missing one. O(n) time, O(1) space. (3) Hash set — insert all, then look up 0..n. O(n) time and space. The XOR approach is the favorite when interviewers worry about integer overflow with large n in some languages; the sum approach is the cleanest one-liner.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • math
  • bit-manipulation
  • hash-set

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Missing Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →