Number of GP sequence

Moderate

0/80

Average time to solve is 10m

4 upvotes

Asked in companies

Problem statement

You are given an array containing ‘N’ integers. You need to find the number of subsequences of length 3 which are in Geometric progression with common ratio ‘R’.

A geometric progression (GP), also called a geometric sequence, is a sequence of numbers that differ from each other by a common ratio. For example, the sequence 2,4,8,16,… is a geometric sequence with common ratio 2.

Note:

As the answer can be very large you need to return the answer in mod 10^9+7.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated positive integers ‘N’ and ‘R’ denoting the number of the elements present in the array and the common ratio of GP.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.

Output Format:

The only line of output of each test case should contain the number of the subsequence of length 3 having a common ratio ‘R’.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
3 <= N <= 10^4  
1 <= R <= 10^4  
1 <= A[i] <= 10^9

Time Limit: 1 sec

Sample Input 1:

2
4 2
3 4 6 12
5 3
2 6 6 18 20

Sample Output 1:

1
2

Explanation for sample input 1:

Test case 1:
The indexes (1 based indexing) of possible subsequence [1,3,4].
The sequence ->  3, 6 (3*2 = 6), 12 ( 3*2*2 = 12) is having first term 3 and common ratio 2.

Test case 2:
The indexes (1 based indexing) of possible subsequence [1,2,4], [1,3,4].
The first sequence ->  2, 6 (2*3 = 6), 18 ( 2*3*3 = 18) is having first term 2 and common ratio 3.
The second sequence is also the same as the first but they only differ in indexes of the middle element.

Sample Input 2:

2
5 5
0 10 1 2 2
6 2
2 4 8 11 22 44

Sample Output 2:

0
2

Hint 1

Hint 2

Check all possible subsequences of length 3.

Approaches (2)

Approach 1

Approach 2

Brute force

We want subsequences of length 3 so we can use 3 nested loops to check all possible subsequences that are in GP or not.
If the first number is A[i] then the next two numbers should be A[i]*R and A[i]*R^2 respectively. If they are matching then we increment our answer by one.
Take mod at each step and finally return the answer.

Time Complexity

O(N^3), where ‘N’ is the number of elements present in the array.

As we ran three nested loops till ‘N’.

Space Complexity

O(1), as we are using constant space.

(100% EXP penalty)

Number of GP sequence

Console