Can Make Arithmetic Progression From Sequence

Easy
257.

Can Make Arithmetic Progression From Sequence

Can Make Arithmetic Progression From Sequence is an easy coding problem on arrays and sorting, asked in Amazon and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canMakeArithmeticProgression = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Sorting puts the candidate progression in order; there is no other arrangement to try.

  2. Hint 2

    Then check that every adjacent gap matches the first one.

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

  1. Sort a copy.
  2. Return true for length ≤ 2.
  3. Let d = a[1] - a[0]; return whether every a[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 every min + k·d present.

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