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 Sam K., 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

More Math practice problems

See all Math problems →