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

Constraints:

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

Example 1: Input:

nums = [3,0,1]

Output:

2

Explanation: n = 3 (there are 3 numbers in nums). The expected numbers in the range [0,3] are 0, 1, 2, 3. The number 2 is missing from the input array.

Solution

This problem asks us to find the single missing number in a given range. We can solve this efficiently using the summation method.

Approach: Summation Method

  • Calculate Expected Sum: First, determine the sum of all integers from 0 to n (inclusive). We can use the arithmetic series formula: n * (n + 1) / 2. Here, n is the count of numbers in the input array, which also defines the upper bound of our range.
  • Calculate Actual Sum: Next, sum all the numbers that are present in the nums array.
  • Find Missing Number: The difference between the expected sum (the sum of all numbers that should be there) and the actual sum (the sum of numbers that are there) will reveal the missing number.

Complexity:

  • Time: O(n), as we iterate through the array once to calculate its sum.
  • Space: O(1), as we only use a few constant extra variables.

Code Example (Python):

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        # Calculate the sum of numbers from 0 to n (inclusive)
        # Using integer division // to ensure an integer result
        expected_sum = n * (n + 1) // 2
        
        # Calculate the sum of numbers present in the array
        actual_sum = sum(nums)
        
        # The missing number is the difference
        return expected_sum - actual_sum