Can Make Arithmetic Progression From Sequence

Problem Description

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.

Key Insights

• An arithmetic progression has a constant difference between consecutive terms.
• To determine if an array can be rearranged into an arithmetic progression, sort the array and check the differences between consecutive elements.
• If the differences between all consecutive elements are the same after sorting, the array can form an arithmetic progression.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting step, where n is the length of the array.
Space Complexity: O(1) - if sorting is done in place, or O(n) if a new array is created for sorting.

Solution

To solve the problem, we can follow these steps:

1. Sort the input array.
2. Calculate the difference between the first two elements in the sorted array.
3. Iterate through the sorted array and verify if the difference between each consecutive pair of elements matches the initial difference.
4. If all differences match, return true; otherwise, return false.

We utilize a sorting algorithm to rearrange the elements, and a single pass through the sorted array to check the differences.

Code Solutions