# LC 1502. Can Make Arithmetic Progression From Sequence

### [Problem link](https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/)

###### tags: `leedcode` `python` `easy`

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 <code>arr</code>, return <code>true</code> if the array can be rearranged to form an **arithmetic progression** . Otherwise, return <code>false</code>.

**Example 1:**

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:**

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

**Constraints:**

- <code>2 <= arr.length <= 1000</code>
- <code>-10⁶ <= arr[i] <= 10⁶</code>

## Solution 1

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()

        d = arr[1] - arr[0]

        for i in range(2, len(arr)):
            if arr[i] - arr[i - 1] != d:
                return False

        return True

## Solution 2

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        n = len(arr)
        minVal = min(arr)
        maxVal = max(arr)
        if (maxVal - minVal) % (n - 1):
            return False
        
        d = (maxVal - minVal) // (n - 1)
        if d == 0:
            return True

        seen = set()
        for a in arr:
            if (a - minVal) % d or a in seen:
                return False
            seen.add(a)

        return True

## Solution 3 - In-place Modification

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        n = len(arr)
        minVal = min(arr)
        maxVal = max(arr)

        if (maxVal - minVal) % (n - 1):
            return False
        
        d = (maxVal - minVal) // (n - 1)
        i = 0
        while i < n:
            if arr[i] == minVal + i * d:
                i += 1

            elif (arr[i] - minVal) % d:
                return False

            else:
                j = (arr[i] - minVal) // d
                if arr[i] == arr[j]:
                    return False
                arr[i], arr[j] = arr[j], arr[i]

        return True

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(n) |
>| Solution 2 | O(n) | O(n) |
>| Solution 3 | O(n) | O(1) |

## Note
因為輸入為int, 所以公差(d)也必為int.

Sol1:
國中數學, 最直觀的想法.
SC為O(n)是因為python的sort採用Timsort, Timsort = Merge Sort + Insertion Sort, Timsort 的 SC = O(n)
[Timsort](https://mailtojacklai.medium.com/%E6%BC%94%E7%AE%97%E6%B3%95-timsort-%E4%BB%A5%E4%BA%BA%E5%91%BD%E5%90%8D%E7%9A%84%E6%8E%92%E5%BA%8F%E6%B3%95-5d5e6ed7872c)

Sol2:

if (maxVal - minVal) % (n - 1):
    return False        # means d != integer, so return False

d = (maxVal - minVal) // (n - 1)
if d == 0:
    return True        # means arr like [1,1,1]

Sol3:
基本上就是這題的follow-up, 難度應該在medium吧.
[leetcode solution](https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/editorial/)