Problem

A sequence of numbers is called 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 to form an arithmetic progression. Otherwise, return false.

Examples

Example 1:

1
2
3

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:

1
2
3

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

Solution

Method 1 - Using AP formula

Here is the approach:

  1. Sort the Array: Sorting the array will help in checking if the consecutive numbers have the same difference.
  2. Check Consecutive Differences: Traverse the sorted array and check if the difference between any two consecutive elements is constant.
  3. Return Result: If all consecutive differences are the same, return true. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr); // Step 1: Sort the array

        int difference =
            arr[1] - arr[0]; // Step 2: Calculate the initial difference

        // Step 3: Check consecutive differences
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] - arr[i - 1] != difference) {
                return false;
            }
        }

        return true; // Step 4: All differences are the same, return True
    }
}
1
2
3
4
5
6
7
8
9

def canMakeArithmeticProgression(arr):
    arr.sort()  # Step 1: Sort the array

    difference = arr[1] - arr[0]  # Step 2: Calculate the initial difference

    # Step 3: Check consecutive differences
    for i in range(2, len(arr)):
        if arr[i] - arr[i - 1] != difference:
            return False

Complexity

  • Time: O(n log n), where n is the number of elements in the array.
  • Space: O(n), but aux space is O(1)