Missing Number

Problem Statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in that range that is missing from the array.

What to notice first

• The array has exactly n elements but covers a range of n+1 values (0 through n), so exactly one is missing.
• The Gauss sum formula computes the expected total for 0..n in one line — subtract the actual sum and the difference is the missing number.
• Distinct elements are guaranteed, so no duplicates complicate the count.

Examples

Input	Output	Explanation
[3, 0, 1]	2	Range 0–3, 2 is missing
[0, 1]	2	Range 0–2, 2 is missing
[9,6,4,2,3,5,7,0,1]	8	Range 0–9, 8 is missing

Constraints

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

Real-World Applications

Where this pattern appears

• Sequence gap detection — find the missing invoice number in an accounting sequence.
• Packet loss detection — given a list of received packet sequence numbers, identify which one was dropped.
• Employee ID audit — confirm which ID in a contiguous range was never assigned.
• Memory address validation — check that all expected memory page indices are accounted for.

Complexity Comparison

Approach	Time	Space	Best When
Hash Set	O(n)	O(n)	Quick to write and easy to understand
Gauss Sum	O(n)	O(1)	Memory is constrained; elegant one-liner

Which approach should you learn first?

• Learn Gauss Sum first — it demonstrates a beautiful mathematical insight and is O(1) space.
• Use Hash Set as a fallback if you forget the formula; it is correct and the same time complexity.

Elegant & Optimal

Gauss Sum

O(n) time · O(1) space

Easy to Remember

Hash Set

O(n) time · O(n) space

Approach 1: Gauss Sum (Math)

★ Recommended

The sum of all integers from 0 to n is given by the Gauss formula: n * (n + 1) / 2. Subtract the actual sum of nums from this expected total. The difference is precisely the missing number.

⏱ Time O(n) One pass to sum 💾 Space O(1) Two integer variables

Step-by-step Example

Input: [3, 0, 1], n = 3

Step	Calculation	Value
Expected sum (0+1+2+3)	3 × 4 / 2	6
Actual sum (3+0+1)	3 + 0 + 1	4
Missing	6 − 4	2

Animated walkthrough

How the Gauss formula pinpoints the missing number

Use Next or Autoplay to see the expected total computed, the actual sum accumulated, and the difference revealed.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) / 2
    return expected - sum(nums)

Solution Code

Python

missing_number_math.py

from typing import List


def missing_number(nums: List[int]) -> int:
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)


print(missing_number([3, 0, 1]))           # 2
print(missing_number([0, 1]))              # 2
print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8

C++

missing_number_math.cpp

#include <numeric>
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expected = n * (n + 1) / 2;
        return expected - accumulate(nums.begin(), nums.end(), 0);
    }
};

Java

missing_number_math.java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2;
        int actual = 0;
        for (int num : nums) actual += num;
        return expected - actual;
    }
}

JavaScript

missing_number_math.js

function missingNumber(nums) {
    const n = nums.length;
    const expected = n * (n + 1) / 2;
    const actual = nums.reduce((sum, n) => sum + n, 0);
    return expected - actual;
}

Rust

missing_number_math.rs

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let expected = n * (n + 1) / 2;
        let actual: i32 = nums.iter().sum();
        expected - actual
    }
}

Go

missing_number_math.go

package golang
func missingNumber(nums []int) int {
  n := len(nums)
  expected := n * (n + 1) / 2
  actual := 0
  for _, num := range nums {




}  return expected - actual  }    actual += num

Approach 2: Hash Set

✓ Simple

Build a set from nums, then iterate 0 through n and return the first value that is not in the set.

⏱ Time O(n) Two passes 💾 Space O(n) Set stores n elements

Step-by-step Example

Input: [3, 0, 1]

Check	In set?
0	Yes
1	Yes
2	No → return 2

Pseudocode

function missingNumber(nums):
    seen = set(nums)
    for value in range(len(nums) + 1):
        if value not in seen:
            return value

Solution Code

Python

missing_number_hash_set.py

from typing import List


def missing_number(nums: List[int]) -> int:
    seen = set(nums)
    for value in range(len(nums) + 1):
        if value not in seen:
            return value
    return -1

C++

missing_number_hash_set.cpp

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> seen(nums.begin(), nums.end());
        for (int value = 0; value <= nums.size(); value++) {
            if (!seen.count(value)) return value;
        }
        return -1;
    }
};

Java

missing_number_hash_set.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) seen.add(num);
        for (int value = 0; value <= nums.length; value++) {
            if (!seen.contains(value)) return value;
        }
        return -1;
    }
}

JavaScript

missing_number_hash_set.js

function missingNumber(nums) {
    const seen = new Set(nums);
    for (let value = 0; value <= nums.length; value++) {
        if (!seen.has(value)) return value;
    }
    return -1;
}

Rust

missing_number_hash_set.rs

use std::collections::HashSet;

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let seen: HashSet<i32> = nums.iter().copied().collect();
        for value in 0..=(nums.len() as i32) {
            if !seen.contains(&value) {
                return value;
            }
        }
        -1
    }
}

Go

missing_number_hash_set.go

func missingNumber(nums []int) int {
    seen := map[int]bool{}
    for _, num := range nums {
        seen[num] = true
    }
    for value := 0; value <= len(nums); value++ {
        if !seen[value] {
            return value
        }
    }
    return -1
}

Watch for these pitfalls

• Integer overflow: for very large n, n * (n + 1) can overflow a 32-bit integer in C++ and Java — use long or long long.
• The hash set approach adds O(n) space; the sum approach uses only two variables.
• XOR is another O(n)/O(1) approach: XOR every index 0..n with every element — the missing value remains. Worth mentioning as a bonus.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

missing_number_space_optimized.py

"""
Solution for Missing Number
"""

def solve():
    """Implementation for approach 3 of Missing Number"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

missing_number_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Missing Number
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

MissingNumberSpaceOptimized.java

/**
 * Solution for Missing Number
 * Approach 3
 */
public class MissingNumberSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

missing_number_space_optimized.js

/**
 * Solution for Missing Number
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

missing_number_space_optimized.rs

/// Solution for Missing Number
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

missing_number_space_optimized.go

package main

import "fmt"

// Solution for Missing Number
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Two Sum Easy #1
• Contains Duplicate Easy #217
• First Missing Positive ↗ Hard #41
• Find the Duplicate Number ↗ Medium #287

Interview Tips

Key trade-offs to discuss

• Why Gauss sum? It is O(1) space and a single arithmetic expression — demonstrates mathematical thinking.
• XOR alternative: XOR every index 0..n with every element. Pairs cancel; the missing number is left. Equally O(1) space — worth knowing for a follow-up.
• Edge cases: n = 1 with [0] → missing is 1; [1] → missing is 0. Both formulas handle these correctly.
• Overflow: always mention the 32-bit overflow risk for n × (n+1) when n is near 10^4.

← Previous
#242 Valid Anagram Next
#290 Word Pattern →