Count the AP

Hard
0/120
Average time to solve is 65m
profile
Contributed by
5 upvotes
Asked in companies
UberLowe's

Problem statement

Bob and Alice recently learned about the arithmetic progression. Alice found an array ‘A’ of size ‘N’ and wondered how many subsequences of this array of size at least 3 are an arithmetic progression.

A sequence is an arithmetic progression if the difference between one term and the next is a constant.

Bob asked you to help her count the number of such subsequences.

Note: It is guaranteed that the answer fits in 32-bit integer.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains one integer ‘N’, denoting the size of the array.

The following line contains an array ‘A’ of ‘N’ spaced integers denoting the array.
Output Format: 
For each test case, print a single integer denoting the number of such subsequences.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 5
1 <= N <= 10^3
-10^9 <= A[i] <= 10^9 

Time Limit: 1 sec
Sample Input 1:
2
4 
1 2 2 3
3
8 9 -1
Sample Output 1:
2
0
Explanation for Sample Input 1:
In the first test case, there are two arithmetic subsequences with indexes [1, 2, 4] and [1, 3, 4].
In the second test case, there is no arithmetic subsequence with size >= 3.
Sample Input 2:
2
5 
1 2 2 3 4
3 
2 2 2
Sample Output 2:
6 
1
Hint

Can we check all possible subsequences?

Approaches (2)
Brute Force

We can generate all possible subsequences using depth-first search and count the number of subsequences that are of size at least 3 and form an arithmetic progression.  



 

Algorithm: 

  • Initialise ‘ans’ to 0.
  • Generate all possible subsequences using DFS
    • If the size of the subsequence is less than 3, continue.
    • If the subsequence forms an AP, increment ‘ans’ by 1.
  • Return ‘ans’
Time Complexity

O(2 ^ N), where ‘N’ is the size of the array.


 

We are generating all possible subsequences, which takes O(2 ^ N) time.


 

Space Complexity

O(N), where ‘N’ is the size of the array.


 

We will need an array of the size at most ‘N’ to store the subsequences. So final space complexity becomes O(N).


 

Code Solution
(100% EXP penalty)
Count the AP
Full screen
Console