# Can Make Arithmetic Progression From Sequence

### **Problem Statement:-**

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`.

**Link:** [https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/description/](https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/description/)

### **Problem Explanation with examples:-**

**Example 1**

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

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

**Constraints**

* `2 <= arr.length <= 1000`
    
* `-10<sup>6</sup> <= arr[i] <= 10<sup>6</sup>`
    

### Intuition:-

* Sorting the array in any order will bring the elements in order. And an AP is always sorted.
    
* So, we sort the array and check if the difference between any two adjacent elements is the same for all the elements.
    
* If the difference between any two adjacent elements is not the same, then the array is not an AP. So, we return False.
    

### Solution:-

* We sort the array using the sort() function.
    
* We iterate over the array using a for loop considering 3 elements at a time using the range of the for loop as range(len(arr)-2).
    
* We check if the difference between any two adjacent elements is the same. If not, then we return False.
    
* If the difference between any two adjacent elements is the same, then we return True at the end of the for loop.
    

### Code:-

JAVA Solution

```java
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length - 2; i++) {
            if (arr[i + 1] - arr[i] != arr[i + 2] - arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
}
```

Python Solution

```python
class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        for i in range(len(arr)-2):
            if arr[i+1]-arr[i] != arr[i+2]-arr[i+1]:
                return False
        return True
```

### Complexity Analysis:-

**TIME**:-

The time complexity is **O(n log n)**, where n is the length of the input array. This is because the code uses `Arrays.sort()` to sort the array, which has a time complexity of O(n log n). After sorting, it iterates over the array once, performing a constant number of operations for each element.

**SPACE**:-

The space complexity is **O(1)**. It does not use any additional data structures that scale with the input size. Only a constant amount of space is required to store the variables and perform the sorting.

### References:-

* [**Sorting**](https://www.geeksforgeeks.org/sorting-algorithms/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)