Problem

Solution

Intuition

This problem requires us to find the mising number from an array. We are told the array should contain all numbers from 0 to n inclusive.

The easy approach to solving this question would be to create a set of all numbers from 0 to n and remove numbers are they are present in nums. A singular element will be left in the set which we can return as the missing number. This solution is O(n) time complexity, and O(n) space complexity. We can do better however by utilizing a simple math trick.

The sum of consecutive numbers from 0 to n is $\frac{n * (n+1)}{2}$. We can simply subtract our expected sum from the sum of all elements in the given array and this will yield the missing number.

Approach

1. Subract the expected sum, $\frac{n * (n+1)}{2}$ from the sum of the given array. Return this difference.

Complexity

• Time complexity: $O(n)$. We utilize linear time for finding the sum.

• Space complexity: $O(1)$. We utilize constant space.

Code

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        len_nums = len(nums)
        return (len_nums * (len_nums + 1) // 2) - sum(nums)