Last Updated: 11 Nov, 2021
Check AP Sequence
Moderate
Asked in companies
You are given an array containing ‘N’ integers. You need to find if it’s possible to convert the given sequence into an Arithmetic Progression by rearranging the array elements, print “true” if it is possible, else print “false”.
For Example :
If ‘N’ = 5, ‘ARR’ = {2, 4, 10, 8, 6}
You can rearrange ‘ARR’ to now become {2, 4, 6, 8, 10} this is an arithmetic progression. Therefore we will print “true”.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.
The second line of each test case contains N integers ‘ARR’, denoting the array elements.
Output Format :
For each test case, print “true” if the given array can be rearranged to form an A.P., else print “false”.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
3 ≤ N ≤ 5000
-10^9 ≤ ARR[i] ≤ 10^9
Time limit: 1 sec
Approaches
An arithmetic sequence is either a non-increasing or a non-decreasing sequence, depending on the value of difference b/w two consecutive elements of AP. This means that simply sorting and then checking for AP sequence is sufficient. To check for the AP sequence in a sorted array, simply check the difference between adjacent elements is equal.
The steps are as follows :
- Sort the input array ‘ARR’.
- Initialize the value of ‘d’ equal to ARR[1] - ARR[0], now run a FOR loop for variable ‘i’ from 2 to N - 1, for each iteration calculate the value of ARR[i] - ARR[i - 1], if this value is not equal to ‘d’ then return “false” as the given array can’t form an AP sequence after rearranging.
- Finally, return “true”, as we can form an AP sequence by rearranging the input array.
We can solve this faster if we remove the need of sorting the input array, one way to do so is to find the largest and smallest element in the array, the difference them will be equal to (N - 1) * d, this way we can calculate the value of ‘d’ (difference between adjacent terms of AP). Now simply form an AP sequence in form of a Hash-Set or a Hash-Map as it allows insertions and deletions in constant time in an average case, this means we can get rid of the log(..) term that came as a result of using sorting. After forming a Hash-Set we can iterate the array elements and remove them one by one from the Hash-Set. Separately handle the case for an AP sequence with all terms equal to each other (d equal to 0).
The steps are as follows :
- Iterate the input array to find the maximum and minimum element in the array. If both the elements are equal then return “true”, as this is the case for ‘d’ equal to 0.
- Initialize the value of ‘d’ equal to (maxElement - minElement) / (N - 1). Return “false” in case (maxElement - minElement) is not divisible by N - 1.
- Initialize a Hash-Set, and insert all the AP terms in it.
- Iterate the input array, for each element check if it is in the Hash-Set if it is present then delete it from the Hash-Set and move to the next element, else return “false” if it is not present in the Hash-Set.
- Finally, return “true”, as we can form an AP sequence by rearranging the input array.