In some array arr, the values were in arithmetic progression: the values arr[i + 1] - arr[i] are all equal for every 0 <= i < arr.length - 1.
A value from arr was removed that was not the first or last value in the array.
Given arr, return the removed value.
Example 1:
Input: arr = [5,7,11,13] Output: 9 Explanation: The previous array was [5,7,9,11,13].
Example 2:
Input: arr = [15,13,12] Output: 14 Explanation: The previous array was [15,14,13,12].
Constraints:
3 <= arr.length <= 10000 <= arr[i] <= 105Problem Overview: You are given an array that represents an arithmetic progression with exactly one number missing. The array is still sorted and follows the same common difference except for the missing term. Your task is to identify that missing number.
Approach 1: Arithmetic Series Sum Formula (O(n) time, O(1) space)
An arithmetic progression has a predictable total sum based on its first term, last term, and length. The key observation: the full progression should contain n + 1 numbers if the array currently has n. First compute the common difference using (arr[n-1] - arr[0]) / n. With this difference, you can determine what each element of the full sequence should be. Then compute the expected sum of the complete progression and subtract the actual sum of the array to get the missing value.
This approach relies on simple math properties of arithmetic sequences. You iterate once to compute the array sum and use the formula to derive the expected progression. Time complexity is O(n) and space complexity is O(1). It's straightforward and works well when you want a formula-based solution.
Approach 2: Find Common Difference + Traverse (O(n) time, O(1) space)
An arithmetic progression has a constant difference between adjacent elements. Because one number is missing, exactly one adjacent pair will violate this pattern. Start by computing the expected common difference using (arr[n-1] - arr[0]) / n. Then iterate through the array and check the difference between consecutive elements.
If arr[i+1] - arr[i] does not equal the expected difference, the missing value must be arr[i] + diff. This works because the gap appears exactly where the progression skipped a number. The algorithm performs a single linear scan over the array and uses constant extra memory. Time complexity is O(n) and space complexity is O(1).
This method is often easier to reason about because it directly checks the progression property instead of computing sums. It also avoids potential overflow issues that can occur with large arithmetic series sums.
Recommended for interviews: The Find Common Difference + Traverse approach is usually what interviewers expect. It demonstrates understanding of arithmetic progression properties and uses a clean linear scan. The sum formula solution is also valid and shows strong mathematical reasoning, but detecting the broken difference tends to be the most intuitive explanation during interviews.
The sum formula for an arithmetic series is \frac{(a_1 + a_n)n}{2}, where n is the number of terms in the arithmetic series, the first term is a_1, and the last term is a_n.
Since the array given in the problem is an arithmetic series with one missing number, the number of terms in the array is n + 1, the first term is a_1, and the last term is a_n. Therefore, the sum of the array is \frac{(a_1 + a_n)(n + 1)}{2}.
Thus, the missing number is \frac{(a_1 + a_n)(n + 1)}{2} - sum_{i = 0}^n a_i.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Since the array given in the problem is an arithmetic series with one missing number, the first term is a_1, and the last term is a_n. The common difference d is \frac{a_n - a_1}{n}.
Traverse the array, and if a_i neq a_{i - 1} + d, then return a_{i - 1} + d.
If the traversal completes without finding the missing number, it means all numbers in the array are equal. In this case, directly return the first number of the array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Arithmetic Series Sum Formula | — |
| Find Common Difference + Traverse | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Arithmetic Series Sum Formula | O(n) | O(1) | When you want a math-based approach using arithmetic progression formulas |
| Find Common Difference + Traverse | O(n) | O(1) | Best when verifying the progression property and detecting the broken gap |
1228. Missing Number In Arithmetic Progression (LeetCode) • hakunamatasq • 761 views views
Watch 6 more video solutions →Practice Missing Number In Arithmetic Progression with our built-in code editor and test cases.
Practice on FleetCode