Leetcode 1502: Can Make Arithmetic Progression From Sequence

Category: Easy

Problem

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/

Examples

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Input: arr = [3,5,1]

Output: true

Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Input: arr = [1,2,4]

Output: false

Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Solution Approach

In this problem, we are to find that if the array elements follow Arithmetic Progression(AP) or not. The sequence is in AP if any two consecutive number’s difference is the same. For example, the sequence 2,4,6 is in AP as the common difference between 2 consecutive numbers is 2.

For the problem, as the numbers are given in unordered fashion we have to have some order before we check if they can be in AP as if we do in its present state the time and space complexity will skyrocket. After ordering we just have to tell if the common difference stays consistent or not.

Coming to the solution, we first sort the array to give it a proper ordering. Then we find the initial common difference by subtracting the first element in the array from the second. As the constraint says that the array will have minimum 2 elements, that’s why the previous step was possible. Then we iterate over the array from its third element till the end. We check if any difference is not equal to the difference we calculated in the first step. If that is the case then we straight away return false. Otherwise, at the end of the loop, we return true.

Solution code

class Solution {
  public boolean canMakeArithmeticProgression(int[] arr) {
    Arrays.sort(arr);
    int diff = arr[1] - arr[0];
    for(int i=2; i<arr.length ; i++){
      if(arr[i]-arr[i-1]!= diff){
        return false;
      }
    }
    return true;
  }
}

class Solution {

public boolean canMakeArithmeticProgression(int[] arr) {

Arrays.sort(arr);

int diff = arr[1] - arr[0];

for(int i=2; i<arr.length ; i++){

if(arr[i]-arr[i-1]!= diff){

return false;

}

return true;

}

For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂