Missing Number

Ishaan S Published 24 Oct, 2026

A list nums holds n distinct integers, all taken from the range 0 to n inclusive. That range contains n + 1 values, so exactly one of them is absent from the list.

Return the absent value. The list is in no particular order.

Can you do it in linear time with only constant extra memory?

Example 1

Input: nums = [2,4,0,1] Output: 3 Why: n = 4, so the range is 0..4. The list has 0, 1, 2 and 4; 3 is missing.

Example 2

Input: nums = [1,2,0] Output: 3 Why: n = 3, range 0..3. Every value except the top one, 3, is present.

Example 3

Input: nums = [1] Output: 0 Why: n = 1, range 0..1. The list holds 1, so 0 is missing.

Constraints

1 <= n == nums.length <= 10⁴
0 <= nums[i] <= n
All values in nums are distinct.

Pattern Path · Math, Bits & Strings · problem 33 of 169

You know exactly which values should be there. What summary of the full range can you compute without looking at the list?

The sum 0 + 1 + ... + n has a closed form: n · (n + 1) / 2.

Subtract the actual sum of the list from the expected sum; the difference is the missing value. (XOR-ing all indices and values works too, and never overflows.)

Target: O(n) time, O(1) extra space.

Start simple

For each candidate 0..n, scan the list to see whether it is present: O(n²) time; sorting first or using a set brings it to O(n log n) or O(n) time with extra space.

The key idea

The range 0..n is fully known in advance, so compare what the list should add up to with what it does add up to.

The expected total of 0 + 1 + ... + n is n · (n + 1) / 2 (Gauss's formula). Every value except one contributes to both totals, so all of them cancel when you subtract the actual sum, and only the missing value survives.

An equivalent trick uses XOR: XOR together every index 0..n and every element. Each present value appears twice (once as an index, once as an element) and cancels to 0, leaving the missing one. The XOR version is handy in languages with fixed-width integers because it can never overflow, while the sum version is easier to read.

Both run in a single pass and keep just one running number.

Complexity

Time: O(n)
Space: O(1)

Python

class Solution:
    def missingNumber(self, nums):
        n = len(nums)
        expected = n * (n + 1) // 2  # sum of 0..n
        return expected - sum(nums)

JavaScript

var missingNumber = function(nums) {
  const n = nums.length;
  let missing = n * (n + 1) / 2; // sum of 0..n
  for (const x of nums) missing -= x;
  return missing;
};

What the interviewer is checking

It tests whether you exploit the structure of the input (a known, contiguous range) instead of reaching for a set or a sort, and whether you think about integer overflow.

Mistakes to avoid

Forgetting that the missing value can be 0 or n itself.
Summing the range only up to n - 1 (an off-by-one on the upper bound).
Integer overflow of the sum in fixed-width languages; XOR avoids it.

Follow-ups to expect

What if two values are missing? (Use sum and sum of squares.)
What if the list is sorted? (Binary search where nums[i] != i.)
What if values can repeat? (Index marking or cyclic sort.)

In real software

Detecting a lost packet in a numbered sequence or a skipped invoice number is often done with a running checksum like this rather than storing every ID.

Practice next

Topics #033 #t-math-bits Array Bit Manipulation Easy Math Practice