A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.
Given an array of numbers arr, return true if the array can be rearranged to form an arithmetic progression. Otherwise, return false.
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] <= 106To determine if the array can be rearranged to form an arithmetic progression, first sort the array. If the sorted array has a consistent difference between every consecutive pair of elements, it is an arithmetic progression. This approach involves sorting the array and then simply checking the difference between each pair of adjacent elements.
The C code sorts the input array using qsort and then checks if each consecutive pair of elements has the same difference. If they do, the function returns true. Otherwise, it returns false.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the algorithm uses constant extra space.
We can use a HashSet (or similar data structure) to track the number of unique differences between pairs of elements in the array without sorting. If the array can be rearranged into an arithmetic progression, the number of unique differences should equal exactly one when you compare all pairs.
This Python solution calculates the expected difference and checks if every value that should be present in the arithmetic progression exists in the set (array is treated as a set to facilitate O(1) lookup).
Time Complexity: O(n), for the set operations. Space Complexity: O(n) due to using a set.
| Approach | Complexity |
|---|---|
| Sorting and Checking | Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) since the algorithm uses constant extra space. |
| Hash Set for Difference Tracking | Time Complexity: O(n), for the set operations. Space Complexity: O(n) due to using a set. |
can make arithmetic progression from sequence leetcode | leetcode 1502 | Linear Solution • Naresh Gupta • 2,017 views views
Watch 9 more video solutions →Practice Can Make Arithmetic Progression From Sequence with our built-in code editor and test cases.
Practice on FleetCode