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.
1def canMakeArithmeticProgression(arr):
2 arr.sort()
3 diff = arr[1] - arr[0]
4 return all(arr[i] - arr[i - 1] == diff for i in range(2, len(arr)))In Python, this function sorts the array using the sort method and checks if the differences between consecutive sorted elements are consistent.
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).