Intuition:

In this problem, we are given an array of n distinct numbers taken from the range [0, n]. Our task is to find the one number in this range that is missing from the array.

The simplest way to solve this problem is to find the sum of the range [0..n] and compare it with the actual sum of the array. The difference between these two sums is the missing number.

Summary of Solution

Find the missing number by comparing the expected sum with the actual sum.

Code

Here’s the first implementation of this approach:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expectedSum = 0
        for i in range(n+1):
            expectedSum += i
        actualSum = 0
        for i in range(n):
            actualSum += nums[i]
        return abs(expectedSum - actualSum)

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

This code has a time complexity of O(n) because it needs to iterate over the entire input array to calculate the actual sum. The space complexity is O(1) because it uses a constant amount of extra space to store the variables n, expectedSum, and actualSum.

We can simplify this code further while maintaining the same time and space complexity. Here’s an improved version that uses the built-in sum function to calculate both expectedSum and actualSum:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expectedSum = sum(range(n+1))
        actualSum = sum(nums)
        return abs(expectedSum - actualSum)

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!