Sponsored
To determine if the array can be rearranged to form an arithmetic progression, first sort the array. If the sorted array has a consistent difference between every consecutive pair of elements, it is an arithmetic progression. This approach involves sorting the array and then simply checking the difference between each pair of adjacent elements.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the algorithm uses constant extra space.
1public class Solution {
2 public bool CanMakeArithmeticProgression(int[] arr) {
3 Array.Sort(arr);
4 int diff = arr[1] - arr[0];
5 for (int i = 2; i < arr.Length; i++) {
6 if (arr[i] - arr[i - 1] != diff) {
7 return false;
8 }
9 }
10 return true;
11 }
12}This C# solution sorts the array with Array.Sort() and verifies if the common difference between consecutive elements remains constant.
We can use a HashSet (or similar data structure) to track the number of unique differences between pairs of elements in the array without sorting. If the array can be rearranged into an arithmetic progression, the number of unique differences should equal exactly one when you compare all pairs.
Time Complexity: O(n), for the set operations. Space Complexity: O(n) due to using a set.
1def canMakeArithmeticProgression(arr):
2 min_val, max_val, n = min(arr),This Python solution calculates the expected difference and checks if every value that should be present in the arithmetic progression exists in the set (array is treated as a set to facilitate O(1) lookup).