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
- Calculate the expected sum of numbers from
0tonusing the formulan * (n + 1) // 2. - Compute the actual sum of all elements in the input array.
- 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), wherenis 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
1if the element is0, or0if the element is1. - Array with All Elements Present: If all numbers from
0tonare present in the array, the difference between the expected sum and actual sum will be0, indicating no missing number. - Array with Zero as Missing Number: If
0is the missing number, the expected sum will be greater than the actual sum by exactly0.
The solution provided is correct, efficient, and clear. It adheres to the constraints and handles all edge cases appropriately.