1502. Can Make Arithmetic Progression From Sequence
Model: qwen2.5-coder:14b
Topics: Array,Sort
FAANG asked: 1
Acceptance rate: 71.2%
Problem Breakdown
The problem asks us to determine if an array can be rearranged into an arithmetic progression. An arithmetic progression is defined as a sequence where the difference between any two consecutive elements is constant.
Inputs:
- An array of integers
arr.
Outputs:
- A boolean value:
trueif the array can be rearranged into an arithmetic progression, otherwisefalse.
Implicit Constraints and Edge Cases:
- The array length is between 2 and 1000.
- Array elements range from -10^6 to 10^6.
- Duplicates are allowed.
- Negative numbers are possible.
Intuition
A brute-force approach would involve generating all permutations of the array and checking if any permutation forms an arithmetic progression. However, this is computationally expensive with a time complexity of O(n!), which is infeasible given the constraints.
The key insight is that for an array to form an arithmetic progression, once sorted, the difference between consecutive elements should be constant. This leads us to sort the array and then check if the differences between consecutive elements are consistent.
Approach
- Sort the Array: Sort the input array
arr. - Calculate Common Difference: Compute the common difference as the difference between the first two elements of the sorted array.
- Verify Consistency: Iterate through the sorted array and check if the difference between each pair of consecutive elements is equal to the common difference.
- Return Result: If all differences are consistent, return
true. Otherwise, returnfalse.
Complexity Analysis
- Time Complexity: O(n log n) due to the sorting step, where n is the length of the array.
- Space Complexity: O(1) if we sort the array in place. If we consider the space used by the sorting algorithm (e.g., Timsort), it would be O(log n).
Solution
def canMakeArithmeticProgression(arr):
arr.sort() # Sort the array
common_diff = arr[1] - arr[0] # Calculate the common difference
for i in range(2, len(arr)):
if arr[i] - arr[i - 1] != common_diff:
return False # If any difference is not equal to the common difference, return False
return True # All differences are consistent
Edge Cases Handled
- Empty Input: The problem constraints specify that the array length is between 2 and 1000, so this case does not apply.
- Duplicates: Duplicates are allowed and handled naturally by sorting. If all elements are the same, they will form a valid arithmetic progression with a common difference of 0.
- Negative Numbers: Negative numbers are handled correctly by the sorting and difference calculation.
- Overflow: The problem constraints ensure that the array elements fit within the specified range, so overflow is not an issue.