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

  • The array nums contains n distinct numbers.
  • The numbers are guaranteed to be in the range [0, n].
  • n represents the length of the array nums.

Example:

Input: nums = [3,0,1]
Output: 2
Explanation: Here, n = 3 (since there are 3 numbers). The full range of numbers should be [0, 1, 2, 3]. The number 2 is missing from the input array.

Solution

We can solve this problem efficiently using a few different approaches.

  • Summation Method:

    • Calculate the expected sum of all numbers from 0 to n using the formula n * (n + 1) / 2.
    • Calculate the actual sum of all elements present in the nums array.
    • The missing number is simply the difference between the expected sum and the actual sum.
    • This approach has an O(n) time complexity (for summing elements) and **O(1) space complexity`.

  • XOR Method (Alternative):

    • Initialize a variable missing with n.
    • Iterate from 0 to n-1. In each step, XOR missing with both i (the expected number) and nums[i] (the actual number).
    • Due to the property a ^ a = 0 and a ^ 0 = a, all numbers present in both the expected range and the array will cancel out, leaving only the missing number.
    • This also has O(n) time complexity and O(1) space complexity and avoids potential overflow issues with large n.

Let's provide the Summation Method solution:

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