1502.-can-make-arithmetic-progression-from-sequence.md

1502. Can Make Arithmetic Progression From Sequence

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

Solution (Python)

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        mini=min(arr)
        length=len(arr)
        difference=max(arr)-mini
        if difference==0:
            return True
        gap=difference/(length-1)
        s=set(n-mini for n in arr)
        return len(s)==length and all(diff % gap == 0 for diff in s)

Solution (C)

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

bool canMakeArithmeticProgression(int* arr, int arrSize){
    qsort(arr, arrSize, sizeof(int), cmpfunc);
    int gap=arr[1]-arr[0];
    for (int i=1;i<arrSize;i++)
    {
        if (arr[i]-arr[i-1]!=gap)
        {
            return false;
        }
    }
    return true;
}

This solution should be O(n log n + n) since it has been sorted first (uses O(n log n)) and then went over every node once.