Can Make Arithmetic Progression From Sequence

The problem requires us to determine if we can rearrange an array such that it forms an arithmetic progression. An arithmetic progression is a sequence where the difference between any two consecutive numbers is constant.

Here’s a simple approach to solving this problem:

1. Sort the array in increasing order.
2. Determine the common difference by subtracting the first element from the second one.
3. Check if every adjacent pair of elements has this common difference. If not, return False.
4. If the loop completes without returning False, return True.

Python solution:

1
2
3
4
5
6
7
8

class Solution:
    def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
        arr.sort()
        diff = arr[1] - arr[0]
        for i in range(2, len(arr)):
            if arr[i] - arr[i-1] != diff:
                return False
        return True

This works by first sorting the array, which allows us to easily determine if a constant difference exists between consecutive elements. The time complexity of this solution is O(n log n) due to the sorting operation, where n is the length of the array. This solution satisfies the constraints 2 <= arr.length <= 1000 and -106 <= arr[i] <= 106.

The basic building block of the solution is pairwise comparison. Am I right?

Yes, you are correct. The basic building block of the solution to this problem is indeed a pairwise comparison.

After sorting the array, we compare each pair of adjacent numbers to check if the difference between them is the same as the difference between the first two elements.

We start from the second index (i=2) because we already know the difference between the first two elements (arr[1] - arr[0]). We then check that this common difference is maintained for all subsequent pairs.

If we encounter a pair where the difference is not equal to the common difference, we immediately return False, as this means that the array cannot be rearranged to form an arithmetic progression.

If we reach the end of the array without finding such a pair, we return True because it means that the array can indeed be rearranged to form an arithmetic progression.

Yes, you are right. The basic building block of the solution is pairwise comparison. In each iteration of the loop, the function compares the difference between two consecutive elements in the array. If the difference is not the same, then the function returns False. Otherwise, the function continues to the next iteration.

The pairwise comparison is necessary because it is the only way to determine if the array can be rearranged to form an arithmetic progression. If all of the differences are the same, then the array can be rearranged to form an arithmetic progression. However, if even one of the differences is different, then the array cannot be rearranged to form an arithmetic progression.

The pairwise comparison is also efficient because it only takes a constant amount of time to compare two numbers. This means that the function can quickly determine if the array can be rearranged to form an arithmetic progression.