Coding problem · Easy · Basics

Find the Missing Number

Easy Algorithms & data structures

nums contains n distinct numbers taken from 0, 1, 2, ..., n, so exactly one number in that range is missing. Return it.

Example 1

Input: nums = [3,0,1]
Output: 2

Example 2

Input: nums = [0,1]
Output: 2

Example 3

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Hints

Hint 1

The sum of 0..n is n × (n + 1) / 2.

Hint 2

Subtract the actual sum of the array from the expected sum.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Gauss's formula gives the expected total n(n+1)/2; the difference from the real total is the missing number. O(n) time, O(1) space, no sorting needed.

Reference solution

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

function missingNumber(nums: number[]): number {
  const n = nums.length;
  return (n * (n + 1)) / 2 - nums.reduce((a, b) => a + b, 0);
}

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

<?php

function missingNumber(array $nums): int
{
    $n = count($nums);
    return intdiv($n * ($n + 1), 2) - array_sum($nums);
}

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

Was this page helpful?