Can Make Arithmetic Progression From Sequence — Solution
Can Make Arithmetic Progression From Sequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Can Make Arithmetic Progression From Sequence is an easy coding problem on arrays and sorting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sequence is an arithmetic progression if the difference between any two consecutive elements is the same.
Given an array of numbers arr, return true if the array can be rearranged into an arithmetic progression.
Example 1
Input: arr = [3,5,1]
Output: true
Explanation: Rearranged as [1,3,5], the common difference is 2.
Example 2
Input: arr = [1,2,4]
Output: false
Example 3
Input: arr = [7,7]
Output: true
Explanation: Any two elements form a progression.
Constraints
2 <= arr.length <= 40-1000 <= arr[i] <= 1000
Hints for Can Make Arithmetic Progression From Sequence
Hint 1
Sorting puts the candidate progression in order; there is no other arrangement to try.
Hint 2
Then check that every adjacent gap matches the first one.
Hint 3
Arrays of length two always qualify.
How to solve Can Make Arithmetic Progression From Sequence
An arithmetic progression is sorted (or reverse sorted), so sort and check that every adjacent gap equals the first.
Approach
- Sort a copy.
- Return
truefor length ≤ 2. - Let
d = a[1] - a[0]; return whether everya[i] - a[i-1] == d.
Why it works
If a rearrangement into a progression exists, the sorted order is that progression (with non-negative difference), so checking the sorted order is sufficient as well as necessary.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- An O(n) version uses min, max and a set:
d = (max - min) / (n - 1)must be integral and everymin + k·dpresent.
Reference solution
Python
def canMakeArithmeticProgression(arr) -> bool:
a = sorted(arr)
if len(a) <= 2:
return True
d = a[1] - a[0]
return all(a[i] - a[i - 1] == d for i in range(2, len(a)))Java
public static boolean canMakeArithmeticProgression(int[] arr) {
int[] a = Arrays.copyOf(arr, arr.length);
Arrays.sort(a);
if (a.length <= 2) return true;
int d = a[1] - a[0];
for (int i = 2; i < a.length; i++) {
if (a[i] - a[i - 1] != d) return false;
}
return true;
}C++
bool canMakeArithmeticProgression(vector<int>& arr) {
vector<int> a = arr;
sort(a.begin(), a.end());
if (a.size() <= 2) return true;
int d = a[1] - a[0];
for (size_t i = 2; i < a.size(); i++) {
if (a[i] - a[i - 1] != d) return false;
}
return true;
}JavaScript
var canMakeArithmeticProgression = function(arr) {
const a = arr.slice().sort(function(x, y) { return x - y; });
if (a.length <= 2) return true;
const d = a[1] - a[0];
for (let i = 2; i < a.length; i++) {
if (a[i] - a[i - 1] !== d) return false;
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms