1502.Can Make Arithmetic Progression From Sequence
===

###### tags: `Easy`,`Array`,`Sorting`

[1502. Can Make Arithmetic Progression From Sequence](https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/)

### 題目描述

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

### 範例

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

* 2 <= `arr.length` <= 1000
* -10^6^ <= `arr[i]` <= 10^6^

### 解答

#### C#

public bool CanMakeArithmeticProgression(int[] arr) {
    Array.Sort(arr);
    for(int i = arr.Length - 1; i >= 2; i--){
        if(arr[i] - arr[i - 1] != arr[1] - arr[0]){
            return false;
        }
    }
    return true;
}

>[name=Jim][time=Jun 6, 2023]

#### C++

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        int n = arr.size();
        if (n == 2) {
            return true;
        }
        sort(arr.begin(), arr.end());
        int commonDiff = arr[0] - arr[1];
        for (int i = 1; i < n - 1; i ++) {
            if (arr[i] - arr[i + 1] != commonDiff) {
                return false;
            }
        }
        return true;
    }
}; 

> [name=Jerry Wu][time=6 June, 2023]

#### Javascript

function canMakeArithmeticProgression(arr) {
  arr.sort((a, b) => a - b);
  const r = arr[1] - arr[0];
  for (let i = 2; i < arr.length; i++) {
    if (arr[i] - arr[i - 1] !== r) return false;
  }

  return true;
}

> [name=Marsgoat][time=6 June, 2023]

看解答看到 $O(n)$ 解，前面太直覺就用sort了，沒想到這題還可以這麼秀

function canMakeArithmeticProgression2(arr) {
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const n = arr.length;
  const r = (max - min) / (n - 1); // 找到公差
  const set = new Set(arr);
  if (r === 0) return true;
  if (r % 1 !== 0) return false;
  for (let i = 0; i < n; i++) {
    if (!set.has(min + i * r)) return false;
  }

  return true;
}

> [name=Marsgoat][time=6 June, 2023]

#### Python

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr = sorted(arr)
        r = arr[1] - arr[0]

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

        return True

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

        r = (mx - mn) // (n - 1)  # 算公差

        st = set()
        for num in arr:
            if (num - mn) % r:
                return False
            st.add(num)

        return len(st) == n

仿照上面公差的寫法
TC: $O(n)$
SC: $O(n)$
> [name=Ron Chen][time=Tue, June 7, 2023]

#### Java

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int r = arr[1] - arr[0];

        for(int i = 2; i < arr.length; i++) {
            if(arr[i] - arr[i-1] != r)
                return false;
        }

        return true;
    }
}

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();
        int n = arr.length;

        if(max - min == 0)
            return true;
        if((max - min) % (n - 1) != 0)
            return false;

        int r = (max - min) / (n - 1);
        Set<Integer> set = new HashSet<>();

        for(int num : arr) {
            if((num - min) % r != 0)
                return false;
            set.add(num);
        }

        return set.size() == n;
    }
}

仿照上面公差的寫法
TC: $O(n)$
SC: $O(n)$
> [name=Ron Chen][time=Tue, June 7, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)