Check AP Sequence

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in companies
SAP LabsSprinklr

Problem statement

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
2 4 10 8 6
4
2 4 6 9
Sample Output 1 :
true
false
Explanation For Sample Input 1 :
For test case 1 :
We will print “true” because:
Then given array can be rearranged as {2, 4, 6, 8, 10} which is an AP.

For test case 2 : 
We will print “false” because:
There is no way to rearrange the input array so that it forms an AP.
Sample Input 2 :
2
5
2 4 8 16 32
6
1 1 1 1 1 1
Sample Output 2 :
false
true
Hint

Try to sort the array and then check for AP sequence.

Approaches (2)
Sorting

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 :

  1. Sort the input array ‘ARR’.
  2. 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.
  3. Finally, return “true”, as we can form an AP sequence by rearranging the input array.
Time Complexity

O( N * log ( N ) ), where N denotes the size of the array.

 

Sorting an array of size N takes time equal to N*log(N).

Hence the time complexity is O( N * log ( N ) ).

Space Complexity

O( 1 )

 

No auxiliary space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Check AP Sequence
Full screen
Console