algoadvance

Given an array of numbers arr, determine if the array can be rearranged to form an arithmetic progression.

An array forms an arithmetic progression if the difference between consecutive elements is constant.

Example:

1. Input: arr = [3, 5, 1] Output: true Explanation: We can rearrange the array as [1, 3, 5] or [5, 3, 1] for both directions the difference is consistent.

2. Input: arr = [1, 2, 4] Output: false Explanation: No rearrangement can form a valid arithmetic progression.

Constraints:

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

Clarifying Questions

1. Can the elements of the array be negative?
   • Yes, the constraints allow negative numbers.
2. Do we need to check both increasing and decreasing order?
   • No, checking for one direction (usually increasing) is sufficient because if one works, the other is just the reverse and should also work.
3. Are there any duplicate elements allowed in the array?
   • Yes, duplicates are allowed as per the problem constraints.

Strategy

To determine if the elements can form an arithmetic progression:

1. Sort the Array: Sorting the array guarantees that elements are in increasing order. This helps in easily checking the difference between consecutive elements.
2. Check Differences: Calculate the common difference between the first two elements. Traverse the sorted array and check if each pair of consecutive elements has the same difference.

Code

def canMakeArithmeticProgression(arr):
    arr.sort()
    common_diff = arr[1] - arr[0]
    
    for i in range(2, len(arr)):
        if arr[i] - arr[i - 1] != common_diff:
            return False
            
    return True

# Example Usage:
# arr1 = [3, 5, 1]
# print(canMakeArithmeticProgression(arr1)) # Output: True

# arr2 = [1, 2, 4]
# print(canMakeArithmeticProgression(arr2)) # Output: False

Time Complexity

• Sorting: The sort operation takes (O(n \log n)) where (n) is the number of elements in the array.
• Checking Differences: This operation takes (O(n)) since we are iterating through the array once.

Therefore, the overall time complexity is (O(n \log n)).

Conclusion

By sorting the array and then verifying the differences between consecutive elements, we can efficiently determine if the elements can form an arithmetic progression. The provided code follows this approach and ensures the task is completed within the constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?