We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Missing Number

Difficulty: Easy

Problem Description

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

Key Insights

  • The array contains numbers from 0 to n, but one number is missing.
  • The sum of the first n natural numbers can be calculated using the formula n * (n + 1) / 2.
  • By subtracting the sum of the numbers in the array from the expected sum, we can find the missing number.

Space and Time Complexity

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

Solution

To solve the problem, we can use the formula for the sum of the first n natural numbers to determine the expected sum. We then compute the actual sum of the elements in the array and subtract it from the expected sum to find the missing number. This approach only requires constant space, as we are not using any additional data structures.

Code Solutions

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2  # Sum of first n natural numbers
    actual_sum = sum(nums)            # Sum of numbers in the array
    return expected_sum - actual_sum   # The missing number
← Back to All Questions