Can Make Arithmetic Progression From Sequence

Problem Statement

The concept of an arithmetic progression involves a sequence where the difference between any two successive elements is constant throughout the sequence. In this problem, we are provided with an array of integers and the task is to determine if the array can be rearranged in such a way that it forms an arithmetic progression. If it's possible, the function should return true. If it's not possible, the function should return false. This involves examining the elements of the input array and discerning whether there exists a constant difference that can apply between every two consecutive elements following some rearrangement.

Examples

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
• -106 <= arr[i] <= 106

Approach and Intuition

The efficient approach to solve this problem is by understanding the characteristics of an arithmetic progression. Here's a detailed plan:

1. Sort the Array: Initially sort the array in ascending order. This aligns the numbers in their natural sequence, making it straightforward to check for consistent differences between subsequent numbers.

2. Calculate the Difference: After sorting, the expected constant difference can be calculated directly from the first two elements of the sorted array.

3. Verify Consistency: Traverse through the sorted array and compare the difference between every two consecutive elements with the calculated difference. If at any point the difference is not consistent with others, return false.

4. Return True if Successful: If the array completes the verification loop without discrepancies, it confirms that the array can indeed form an arithmetic progression, thus return true.

Why This Works: Sorting helps simulate the necessary condition for forming arithmetic progressions by arranging elements in a natural order. By computing and then validating the consistent difference post-sorting, we efficiently confirm or deny the possibility of arranging the original array into an arithmetic progression. In essence, if a sequence is an arithmetic progression after sorting, then the original sequence can be rearranged into one; if not, then it's impossible.

Solutions

class Solution {
public:
    bool isArithmeticSequence(std::vector<int>& sequence) {
        int minElem = *std::min_element(sequence.begin(), sequence.end());
        int maxElem = *std::max_element(sequence.begin(), sequence.end());
        int elemCount = sequence.size();
            
        if ((maxElem - minElem) % (elemCount - 1) != 0) {
            return false;
        }
            
        int step = (maxElem - minElem) / (elemCount - 1);
        int index = 0;
            
        while (index < elemCount) {
            // Check if current element is at the correct position
            if (sequence[index] == minElem + index * step) {
                index++;
            // Element does not match the expected value of the arithmetic sequence
            } else if ((sequence[index] - minElem) % step != 0) {
                return false;
            // Correct position for the current element
            } else {
                int targetIndex = (sequence[index] - minElem) / step;
                    
                // Duplicate check, sequence can't have repeating values at correct indices
                if (sequence[index] == sequence[targetIndex]) {
                    return false;
                }
                    
                // Swap to move the element into its expected position
                std::swap(sequence[index], sequence[targetIndex]);
            }
        }
            
        return true;
    }
};