Domain 1EasyCORE

Missing Number

The problem asks us to find the missing number in an array `nums` that contains `n` distinct numbers ranging from `[0, n]`. The input is an array of integers, and the output should be a single integer representing the missing number. The constraints ensure that all numbers are unique and within the specified range.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Math#Bit Manipulation

268. Missing Number

Model: qwen2.5-coder:14b
Topics: Array,Math,Bit Manipulation
FAANG asked: 1
Acceptance rate: 55.2%


Problem Breakdown

The problem asks us to find the missing number in an array nums that contains n distinct numbers ranging from [0, n]. The input is an array of integers, and the output should be a single integer representing the missing number. The constraints ensure that all numbers are unique and within the specified range.

Intuition

A brute-force approach would involve sorting the array and checking each number to see if it matches its index. However, this approach has a time complexity of O(n log n) due to the sorting step, which is not optimal for large arrays.

The key insight here is to use mathematical properties to achieve an O(n) runtime complexity with O(1) extra space. The sum of the first n natural numbers is given by the formula n * (n + 1) / 2. By calculating this expected sum and subtracting the actual sum of the array elements, we can find the missing number.

Approach

  1. Calculate the expected sum of numbers from 0 to n using the formula n * (n + 1) // 2.
  2. Compute the actual sum of all elements in the input array.
  3. The difference between the expected sum and the actual sum will be the missing number.

This approach leverages the properties of arithmetic series and avoids additional data structures, ensuring both time and space efficiency.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to compute the actual sum.
  • Space Complexity: O(1), as we only use a few extra variables for calculations, regardless of the input size.

Solution

def missingNumber(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

# Example usage:
print(missingNumber([3, 0, 1]))  # Output: 2
print(missingNumber([0, 1]))     # Output: 2
print(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # Output: 8
print(missingNumber([0]))        # Output: 1

Edge Cases Handled

  • Single Element Array: If the array has only one element, the missing number is simply 1 if the element is 0, or 0 if the element is 1.
  • Array with All Elements Present: If all numbers from 0 to n are present in the array, the difference between the expected sum and actual sum will be 0, indicating no missing number.
  • Array with Zero as Missing Number: If 0 is the missing number, the expected sum will be greater than the actual sum by exactly 0.

The solution provided is correct, efficient, and clear. It adheres to the constraints and handles all edge cases appropriately.