You are given an array nums containing n distinct numbers in the range [0, n]. Your task is to find and return the only number in the range that is missing from the array.

  • n is the length of nums.
  • 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 (length of array). The range is [0,3]. Numbers in array are 0, 1, 3. The missing number is 2.

Solution

Several approaches can solve this problem efficiently.

  • Approach 1: Summation
    • Calculate the expected sum of all numbers from 0 to n using the formula n * (n + 1) / 2.
    • Calculate the actual sum of all numbers present in the nums array.
    • The missing number is simply the expected_sum - actual_sum.
    • This approach has O(n) time complexity and O(1) space complexity.
  • Approach 2: XOR (Bit Manipulation)
    • Initialize a variable missing with n.
    • Iterate from i = 0 to n-1. For each i and the corresponding number num at nums[i]:
      • missing = missing ^ i ^ num
    • The final value of missing will be the missing number. This works because XORing a number with itself results in 0, and XORing with 0 returns the number itself. All present numbers (both i and nums[i]) will cancel out, leaving only the missing one.
    • This approach also has O(n) time complexity and O(1) space complexity, and is robust against potential integer overflow for very large n where the sum might exceed standard integer limits (though not a concern for the given constraints of n <= 10^4).

Let's use the Summation approach for the code example:

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