Skip to main content
Talentd

Missing Number In Arithmetic Progression - Solution & Explanation

EasyPremiumFree on FleetCodeArrayMath10 min readAsked at: Amazon, Audible
Practice this problem

Problem Statement

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 <= 1000
  • 0 <= arr[i] <= 105
  • The given array is guaranteed to be a valid array.

Approach Overview

Problem 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.

Approach 1: Arithmetic Series Sum Formula

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 2: Find Common Difference + Traverse

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Arithmetic Series Sum Formula—
Find Common Difference + Traverse—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Arithmetic Series Sum FormulaO(n)O(1)When you want a math-based approach using arithmetic progression formulas
Find Common Difference + TraverseO(n)O(1)Best when verifying the progression property and detecting the broken gap

Video Solution

1228. Missing Number In Arithmetic Progression (LeetCode) • hakunamatasq • 790 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Missing Number In Arithmetic Progression easy or hard?
LeetCode classifies this problem as Easy because it relies on basic arithmetic progression properties and a simple linear scan of the array. The challenge is recognizing how to compute the expected common difference and detect where the pattern breaks.
Missing Number In Arithmetic Progression Python/Java solution
Both Python and Java implementations follow the same idea: compute the common difference and iterate through the array until the difference between adjacent elements changes. At that point, return arr[i] + diff. The algorithm runs in O(n) time with constant extra space.
How to solve Missing Number In Arithmetic Progression in O(n)?
First compute the expected common difference using (arr[n-1] - arr[0]) / n. Then iterate through the array and compare arr[i+1] - arr[i] with the expected difference. When the difference is larger than expected, the missing number must be arr[i] + diff.
What is the best approach for Missing Number In Arithmetic Progression?
The most common approach is computing the expected common difference and scanning the array to find where the difference breaks. Once a pair of adjacent elements does not match the expected difference, the missing number is simply the previous value plus the difference. This solution runs in O(n) time and O(1) space.
Is Missing Number In Arithmetic Progression asked at Google/Amazon/Meta?
Arithmetic progression and missing-number problems appear frequently in interviews at companies like Amazon, Google, and Microsoft. They test your understanding of mathematical patterns, array traversal, and edge-case reasoning.
What data structure is used in Missing Number In Arithmetic Progression?
The problem primarily uses arrays and simple arithmetic operations. No advanced data structures are required since the progression property allows you to detect the missing value with a linear scan.
What is the time complexity of Missing Number In Arithmetic Progression?
The optimal solution runs in O(n) time because you only need a single pass through the array to detect where the arithmetic progression breaks. Both the traversal approach and the arithmetic sum approach also use O(1) extra space.

Ready to solve this problem?

Practice Missing Number In Arithmetic Progression with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays