Last Updated: 30 Dec, 2020
Number of GP sequence
Moderate
Asked in companies
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.
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
Approaches
- 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.
- If the three terms of GP are A, A*R, A*R^2 then we can rewrite them in the form of A/R, A, A*R. Now if we fix the middle element and somehow get the count of A/R lying on the left side and A*R lying on the right side then we can multiply those counts to get the total number of subsequences.
- To get the count we can use two hashmaps one will store the frequency of all elements lying on the left side of the current element and the other will store the frequency of all elements lying on the right side of the current element. For simplicity, let’s name them left hashmap and right hashmap.
- Initially, we insert all the elements in the right hashmap and delete elements one by one from it as we traverse the array to get the frequency of elements present in a suffix.
- Similarly, the left hashmap will be empty initially and we add the element in it while traversing the array to get the frequency of element present in prefix.
- If we are on some ith element then we first remove one occurrence of it from the right hashmap and then for this element to be a part of subsequence we must check if it is divisible by ‘R’ or not because the first term will be A[i]/R and if it is not divisible by ‘R’ that means the first term is not possible hence this element is not a part of subsequence.
- Now if this element is part of subsequence then we get the count of A[i]/R from the left hashmap and count of A[i]*R from the right hashmap and add the product of counts in our answer.
- After the calculation, we must add this current element to our left hashmap as this element will serve as a prefix for the rest of the elements lying ahead of it.