Skip to main content

268. Missing Number

easy

An array contains n distinct integers from 0 to n with one number missing. Find the missing one in O(n) time and O(1) space using XOR — or a Gaussian-sum subtraction.

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

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

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

Sum approach: expected = n*(n+1)/2; missing = expected - sum(nums). Watch for integer overflow on large n.

Hint 2

XOR approach: XOR every index 0..n together with every value in nums. Pairs cancel; the missing number survives.

Hint 3

Both are O(n) time and O(1) space — pick whichever you can derive without bugs on the whiteboard.

Solution approach

Reveal approach

XOR approach (overflow-proof). Initialize result = n (since the index range goes 0..n-1 but the value range goes 0..n, we seed with n to cover the boundary). For each index i from 0 to n-1, do result ^= i ^ nums[i]. Every value that appears as both an index and an element cancels out; only the missing value remains. O(n) time, O(1) space. The arithmetic alternative computes expected_sum = n * (n + 1) / 2 then subtracts the actual sum of nums; equally O(n)/O(1) but vulnerable to integer overflow in fixed-width languages on adversarial inputs.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • bit-manipulation
  • xor
  • math

Related problems

Asked at

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

  • Amazon
  • Google
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →