Check Arithmetic Progression

Given an array of N integers. Write a program to check whether an arithmetic progression can be formed using all the given elements. If possible print “YES”, else print “NO”. Input: First line of input contains a single integer T which denotes the number of test cases. Then T test cases follows. First line of each test case contains a single integer N which denotes number of elements in the array. Second line of each test case contains N space separated integers which denotes elements of the array. Output: For each test case, print "YES" without quotes if an arithmetic progression can be formed using all the given elements, else print "NO" without quotes. Constraints: 1<=T<=100 1<=N<=105 1<=Arr[i]<=105 Example: Input: 2 4 0 12 4 8 4 12 40 11 20 Output: YES NO

class Solution {
    // O(NlogN) Time & O(1) Space complexity
    public static boolean isAP(int[] arr, int n) {
        if (n <= 2)
            return true;
        Arrays.sort(arr);
        int d = arr[1] - arr[0];
        for (int i = 2; i < n; i++) {
            if (arr[i] - arr[i - 1] != d)
                return false;
        }
        return true;
    }

    // O(N) Time & O(N) Space Complexity
    public static boolean isAP(int[] arr, int n) {
        if (n <= 2)
            return true;
        Set<Integer> set = new HashSet<>();
        int smallest = Integer.MAX_VALUE, smallest2 = Integer.MAX_VALUE;
        for (int x : arr) {
            if (x < smallest) {
                smallest2 = smallest;
                smallest = x;
            } else if (x < smallest2)
                smallest2 = x;
            if (set.contains(x))
                return false;
            set.add(x);
        }
        int diff = smallest2 - smallest;
        int current = smallest, count = 0;
        while (set.contains(current)) {
            current = current + diff;
            count++;
        }
        return count == n;
    }
}