LeetCode Solutions Blog

Missing Number

Number: 268

Difficulty: Easy

Paid? No

Problem Description

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

Key Insights

The range of numbers is continuous from 0 to n, but one number is missing.
The sum of numbers from 0 to n can be computed using the arithmetic sum formula.
Subtracting the sum of the given array from the expected sum gives the missing number.
There is a follow-up challenge to solve the problem in O(n) time and O(1) extra space.

Space and Time Complexity

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

Solution

We compute the expected sum of all numbers from 0 to n using the formula sum = n*(n+1)/2. Then, we compute the actual sum of the numbers in the array. The missing number is obtained by subtracting the actual sum from the expected sum.
This approach uses arithmetic operations (O(1) extra space) and loops over the array once (O(n) time).

Code Solutions

# Function to find the missing number in the array
def missingNumber(nums):
    # Calculate n, where n is the length of the nums array
    n = len(nums)
    # Compute the expected total sum using the arithmetic sum formula for numbers 0 to n
    expected_sum = n * (n + 1) // 2
    # Compute the actual sum of the numbers in the array
    actual_sum = sum(nums)
    # The missing number is the difference between expected and actual sums
    return expected_sum - actual_sum

# Example Usage
print(missingNumber([3, 0, 1]))  # Output: 2