Sorting: Check if the array is Arithmetic Progression

Problem Statement:

You are given an unsorted array.

You need to check if the array is AP.

An array is considered as AP if the difference between any two consecutive terms is always the same.

Example:

Input: 4, 10, 1, 7

Output: Yes

After sorting [1, 4, 7, 10]

Solution 1: Naive Approach

Sort the array

Find the common difference

Check the difference between consecutive elements are same.

Time Complexity: O(n log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool solution(int arr[], int n)
{
    if (n == 1)
        return true;

    sort(arr, arr + n);

    int d = arr[1] - arr[0];

    for (int i = 2; i < n; i++)
        if (arr[i] - arr[i - 1] != d)
            return false;

    return true;
}

int main()
{
    int arr[] = {  4, 10, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    (solution(arr, n)) ? (cout << "Yes" << endl) : (cout << "No" << endl);

    return 0;
}