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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5bool canMakeArithmeticProgression(vector<int>& arr) {
6 sort(arr.begin(), arr.end());
7 int diff = arr[1] - arr[0];
8 for (size_t i = 2; i < arr.size(); ++i) {
9 if (arr[i] - arr[i - 1] != diff) {
10 return false;
11 }
12 }
13 return true;
14}In this C++ solution, we first sort the array and then iterate through it to check if the difference between each pair of consecutive elements is the same.
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).