PROBLEM LINK:
Author: Akshay Venkataramani
Tester: Timothy Jeyadoss
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, STL, Geometric Progression basics
EXPLANATION:
First up, we have corner case when k=1. For this, we simply have to store each element in a map, and if number of occurences of any value is >=3 , let the no. of occurences be n. We have nC3 (recall combinations formula? ) possible ways to choose our triplet. nC3 = (n*(n-1)*(n-2))/6.
Otherwise, we need to incorporate dynamic programming into our solution.
Let us have 3 maps, m1, m2 , m3 , each storing the number of possible ways for a value to be the first term of our GP, second term of our GP, and third term of our GP respectively.
For example, if input is N=6, K=2, and the input array A=[1,1,2,2,4,8]
m1
m1 will be equal to {1,2} , {2,2} , {4,1} , {8,1} . i.e., each term along with the number of ways in which it can be the first term of our GP. Each of these pair of values are present inside m1. {1,2} denotes that 1 can be the first term of our GP in 2 distinct ways. {2,2} denotes that 2 can be the first term of our GP in 2 distinct ways. Similarly, 4 and 8 can be the first term of our GP respectively. For this step, m1[a[i]]++ would do the job.
m2
m2 will be equal to {2,4} , {4,2}, {8,1} IMPORTANT STEP : This is because, 2 can be the second term of our GP in the following ways->choosing first 1, first 2; choosing first 1, second 2; choosing second 1,first 2; Choosing second 1, second 2; Hence, we have the pair {2,4} inside m2.
Similarly, we can perform the same steps for first term of our GP being 2 and second term being 4. There are 2 ways in which 4 can be the second term of our GP-> choosing first 2, and 4; choosing second 2, and 4; Hence, we have the pair {4,2} inside m2.
For 8 being the second term in our GP, we have one way → choosing the only 4 and only 8. Hence we have a pair {8,1} in m2.
This step, can be performed in our code simply by checking if a[i]%k equates to 0. If this is possible, it means a[i] can be the second member of our GP (recall that, if the three terms of our GP are gp[1] , gp[2] and gp[3] , then gp[2]/gp[1] = k and gp[3]/gp[2] = k). Therefore, if a[i]%k is 0, we can have a[i] as the 2nd term of our GP for every a[i]/k being the first term of our GP.
m3
m3 will be equal to {4,4} , {8,2}. This is because, we have 4 ways in which 4 can be the third and final term of our GP , i.e., each combination of {1,2} mentioned in previous step appended with a 4.
Similary, 8 can be the third term of our GP in 2 ways , i.e., each combination of {2,4} mentioned in previous step appended with an 8.
This step can again be performed code wise, by checking if (a[i]%(k2)) is 0. If this is the case, we can have a[i] as the third term of our GP, for every a[i]/k being the second term of our GP. This is where dynamic programming comes into picture.
Hence, in the end, we traverse m3 (Since we need a triplet of GP terms) , and add the value to the answer.
Corner case!! When m3 has a value 0, there’s a chance that it would have considered the same 0 as first, second and third term of the GP. We need to subtract those possibilities from the overall answer carefully. For example, if our array had only one zero present in the input, there would still be an entry {0,1} in m3. This needs to be taken care of properly. [refer author’s solution!]
AUTHOR’S SOLUTION:
Author’s solution can be found here.
