AlgoMaster Logo

Missing Number

Last Updated: March 29, 2026

easy

Understanding the Problem

We have an array of n distinct integers, and these integers come from the range [0, n]. Since the range has n + 1 numbers but the array only holds n of them, exactly one number is missing. Our job is to find it.

The key observation is that we know what the complete set should look like. If n = 3, the full set is {0, 1, 2, 3}. The array gives us 3 of those 4 numbers, and we need to figure out which one got left out. This "known universe" property is what makes the problem tractable. We're not searching for an arbitrary missing value. We know the exact range, and that gives us powerful mathematical tools.

Key Constraints:

  • n == nums.length with 1 <= n <= 10^4 → With n up to 10,000, even O(n^2) would run in about 100 million operations, which is borderline. O(n log n) and O(n) are both comfortable.
  • 0 <= nums[i] <= n → All values fit in the range [0, n], so we could use an auxiliary boolean array of size n+1 if we wanted.
  • All numbers are unique → No duplicates to worry about. Each number from [0, n] appears either zero or one times.

Approach 1: Hash Set

Intuition

The most direct way to find a missing element: put everything you have into a set, then check which number from the expected range isn't there. It's the approach you'd use in everyday programming without thinking twice.

We know the full range is [0, n]. We have n numbers. Dump them into a hash set, then loop from 0 to n and return the first number that's not in the set.

Algorithm

  1. Create a hash set containing all elements of nums.
  2. Loop through every integer from 0 to n (where n is the length of nums).
  3. For each integer, check if it exists in the set.
  4. Return the first integer not found in the set.

Example Walkthrough

1Initial array: nums = [3, 0, 1], n = 3. Build hash set {0, 1, 3}.
0
3
1
0
2
1
1/4

Code

The hash set approach uses O(n) extra space to store every element. What if we could exploit the mathematical properties of the range [0, n] to avoid storing anything at all?

Approach 2: Gauss' Formula (Sum)

Intuition

Here's the key insight: we know exactly what the sum of [0, n] should be. The famous formula n * (n + 1) / 2 gives us the sum of the first n natural numbers. If we compute the actual sum of the array and subtract it from the expected sum, the difference must be the missing number.

Think of it like counting money. If you know a cash register should have $45 (the sum of bills numbered 0 through 9) and you count $37, then $8 worth of bills is missing. Same principle here.

Algorithm

  1. Compute the expected sum: n * (n + 1) / 2 where n is the length of the array.
  2. Compute the actual sum of all elements in nums.
  3. Return expectedSum - actualSum.

Example Walkthrough

1n=9. Expected sum = 9*10/2 = 45. Start computing actual sum.
0
9
1
6
2
4
3
2
4
3
5
5
6
7
7
0
8
1
1/5

Code

The sum approach is already O(n) time and O(1) space. But there's a subtle concern with integer overflow for large n. Is there a bitwise technique that avoids arithmetic altogether?

Approach 3: XOR (Bit Manipulation)

Intuition

XOR has a beautiful property: a ^ a = 0 and a ^ 0 = a. In other words, XOR-ing a number with itself cancels it out, and XOR-ing with zero leaves it unchanged. XOR is also commutative and associative, so the order doesn't matter.

Here's the trick: XOR all the indices from 0 to n together with all the values in the array. Every number that appears in both the index range and the array will cancel out. The only number left standing is the one that exists in the range but not in the array, which is the missing number.

Algorithm

  1. Initialize xor to 0.
  2. XOR xor with each index from 0 to n.
  3. XOR xor with each element of nums.
  4. After all operations, xor holds the missing number. Return it.

Example Walkthrough

1Start: xor=0, n=3. XOR indices [1..n] with array elements.
0
3
1
0
2
1
1/5

Code