Problem statement

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

Example 1

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3, so the range is [0,3]; 2 is absent.

Example 2

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

Constraints

• 1 <= nums.length <= 30
• All numbers are distinct and within [0, nums.length]

Follow-up: can you do it with O(1) extra space using arithmetic or XOR?

Hints for Missing Number

1. Hint 1

   The sum 0+1+…+n is n(n+1)/2 — compare it with the actual sum.

2. Hint 2

   XOR of everything in [0,n] with everything in nums leaves exactly the missing number.

How to solve Missing Number

The array holds n distinct values drawn from 0 .. n, so exactly one is absent. The sum of the complete range is known in closed form — n(n+1)/2 — and subtracting the array's actual sum leaves precisely the missing value.

Approach

1. Let n be the array's length; the full range is 0 .. n.
2. Compute the expected total n * (n + 1) / 2.
3. Sum the array.
4. Return the difference.

Why it works

Every value except one contributes identically to both totals, so the difference cancels them all and isolates the absent one. XOR gives the same result by a similar cancellation — x ^ x == 0, so XOR-ing the array together with 0 .. n leaves only the unpaired value — and has the advantage of never overflowing, which matters when n is large enough for the triangular number to exceed the integer range.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The range is 0 .. n inclusive, which is n + 1 values for an array of length n — using n - 1 in the formula is the usual slip.
• Sorting and scanning works but is O(n log n) for no gain.
• The triangular number can overflow for large n; the XOR variant avoids that entirely.
• The missing value may be 0 or n itself, so no interior assumption is safe.

Reference solution

Python

from typing import List

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

Java

public static int missingNumber(int[] nums) {
    int n = nums.length;
    int total = n * (n + 1) / 2;
    for (int x : nums) total -= x;
    return total;
}

C++

int missingNumber(vector<int>& nums) {
    int n = (int) nums.size();
    int total = n * (n + 1) / 2;
    for (int x : nums) total -= x;
    return total;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy