Given an array of numbers `arr`

. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return `true`

if the array can be rearranged to form an arithmetic progression, otherwise, return `false`

.

**Example 1:**

Input:arr = [3,5,1]Output:trueExplanation: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:**

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

**Constraints:**

`2 <= arr.length <= 1000`

`-10^6 <= arr[i] <= 10^6`

**Solution 1: Sort and check.**

Time complexity: O(nlog)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: bool canMakeArithmeticProgression(vector<int>& arr) { sort(begin(arr), end(arr)); const int diff = arr[1] - arr[0]; for (int i = 2; i < arr.size(); ++i) if (arr[i] - arr[i - 1] != diff) return false; return true; } }; |

## Java

1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public boolean canMakeArithmeticProgression(int[] arr) { Arrays.sort(arr); int diff = arr[1] - arr[0]; for (int i = 2; i < arr.length; ++i) if (arr[i] - arr[i - 1] != diff) return false; return true; } } |

## python3

1 2 3 4 5 |
class Solution: def canMakeArithmeticProgression(self, arr: List[int]) -> bool: arr.sort() diff = arr[1] - arr[0] return all(i - j == diff for i, j in zip(arr[1:], arr[:-1])) |

**Solution 2: Rearrange the array**

Find min / max / diff and put each element into its correct position by swapping elements in place.

Time complexity: O(n)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: bool canMakeArithmeticProgression(vector<int>& arr) { const int n = arr.size(); const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr)); const auto [lo, hi] = pair{*loit, *hiit}; if ((hi - lo) % (n - 1)) return false; const int diff = (hi - lo) / (n - 1); if (diff == 0) return true; for (int i = 0; i < n; ++i) { if ((arr[i] - lo) % diff) return false; const int idx = (arr[i] - lo) / diff; if (idx != i) swap(arr[i--], arr[idx]); } return true; } }; |