1228. Missing Number In Arithmetic Progression
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 51.0%
Problem Breakdown
The problem asks us to find the missing number in an arithmetic progression array where one element has been removed. The input is an array arr of integers, and the output should be the integer that was removed. The constraints are that the array length is between 3 and 1000, and each element is between 0 and 10^5.
Inputs:
- An array
arrof integers representing an arithmetic progression with one missing number.
Outputs:
- An integer representing the missing number in the original arithmetic progression.
Implicit Constraints:
- The first and last elements are not removed.
- The array is guaranteed to have at least three elements, ensuring that there’s enough information to determine the common difference.
Intuition
A brute-force approach would involve generating all possible numbers in the range from the first to the last element of the array and checking which one is missing. However, this approach is inefficient with a time complexity of O(n^2) due to nested loops.
The key insight is that in an arithmetic progression, the difference between consecutive elements is constant. We can use this property to find the common difference by calculating the total expected sum of the array if no number was missing and comparing it to the actual sum of the given array. The difference between these sums will be the missing number.
Approach
- Calculate the common difference
dusing the formula:d = (arr[-1] - arr[0]) // len(arr). - Compute the expected sum of the arithmetic progression if no number was missing.
- Subtract the actual sum of the array from this expected sum to find the missing number.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We need to iterate through the array to calculate the actual sum.
- Space Complexity: O(1), as we only use a few extra variables for calculations.
Solution
def missingNumber(arr):
# Calculate the common difference
d = (arr[-1] - arr[0]) // len(arr)
# Calculate the expected sum of the arithmetic progression
expected_sum = (len(arr) + 1) * (arr[0] + arr[-1]) // 2
# Calculate the actual sum of the array
actual_sum = sum(arr)
# The missing number is the difference between the expected and actual sums
return expected_sum - actual_sum
# Example usage:
print(missingNumber([5, 7, 11, 13])) # Output: 9
print(missingNumber([15, 13, 12])) # Output: 14
Edge Cases Handled
- Common Difference of Zero: If the common difference is zero (i.e., all elements are the same), the expected sum will be equal to the actual sum, and thus the missing number will be the same as any element in the array.
- Single Missing Element: The approach correctly identifies a single missing element between the first and last elements of the array.