Missing Number

How it works

We are given n distinct numbers from the range [0, n], with exactly one number missing.

A simple mathematical observation helps here:

• The sum of numbers from 0 to n is known
• If we subtract the sum of the given array from this expected sum, the result must be the missing number

Instead of computing two separate sums, we can combine both ideas into a single running calculation, which keeps the logic clean and avoids overflow issues in some languages.

This approach uses basic arithmetic, making it easy to understand and language-independent.

Steps

1. Let n be the length of the array.
2. Initialize a variable res = n.
3. For each index i from 0 to n - 1:
   • Add i to res
   • Subtract nums[i] from res
4. After the loop, res will hold the missing number.
5. Return res as the answer.

Complexity

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

Things to watch for

Forgetting That n Could Be the Missing Number

The range is [0, n] for an array of length n, meaning n itself could be missing. Solutions that only check indices 0 to n-1 will miss this case and fail to return n when all other numbers are present.

Integer Overflow in Sum-Based Approach

When using the mathematical approach, computing the full expected sum n * (n + 1) / 2 separately before subtracting can cause overflow for large n. Combining addition and subtraction in a single loop avoids this issue.

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)

        for i in range(len(nums)):
            res += i - nums[i]
        return res

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = nums.size();

        for (int i = 0; i < nums.size(); i++) {
            res += i - nums[i];
        }
        return res;
    }
};