Count Triplets - Hacker Rank Solution

You are given an array and you need to find number of tripets of indices  such that the elements at those indices are in geometric progression for a given common ratio  and .

For example, . If , we have  and  at indices  and .

Function Description

Complete the countTriplets function in the editor below. It should return the number of triplets forming a geometric progression for a given  as an integer.

countTriplets has the following parameter(s):

• arr: an array of integers
• r: an integer, the common ratio

Input Format

The first line contains two space-separated integers  and , the size of  and the common ratio.
The next line contains  space-seperated integers .

Constraints

Output Format

Return the count of triplets that form a geometric progression.

Sample Input 0

4 2
1 2 2 4

Sample Output 0

2

Explanation 0

There are  triplets in satisfying our criteria, whose indices are  and 

Sample Input 1

6 3
1 3 9 9 27 81

Sample Output 1

6

Explanation 1

The triplets satisfying are index , , , ,  and .

Sample Input 2

5 5
1 5 5 25 125

Sample Output 2

4

Explanation 2

The triplets satisfying are index , , , .

Count Triplets - Hacker Rank Solution

The first and easiest solution that comes to our mind is to write  loops, each to fetch an integer for our triplet.

for i from 0 to n-1
    get a[i]
    for j from i+1 to n-1
        get a[j]
        for k from j+1 to n-1
            get a[k]
            //check if the triplet (a[i],a[j],a[k]) satisfies our condition here

But the complexity of this approach is , which will not pass.

Since the common ratio is given, we may try to generate the triplet by multiplying the common ratio to each element, that is  and check if each element is present in our given array. But simply checking if it is present will not do as we need to ensure that index of the number  is greater than  and index of  is greater than  to satisfy the condition . This approach should pass in  or  if implemented correctly.

An elegent solution will be to represent our triplets by (, , ), where r is the common ratio and . So, we need to find  and  where .
We use two maps. Let's call them  and . Initially, in the  map we store the frequency of all the elements. Now, as we traverse the array elements from left side, we first decrement it's count from  map by , then we check the count of  in the  map (say, )and the count of check  in the  map (say, ). We, increment our answer by . At last we increment the count of  in the  map by .
The intuition behind this is the  map will always hold elements which have indices less than the current index and the  map will hold elements which have indices greater than the current index.
Time complexity of this approach: .

Problem Setter's code:

#include<bits/stdc++.h>
using namespace std;

map<long long,long long> l,r;

int main()
{
 long long n, k,ans=0 ;
 scanf("%lld%lld",&n,&k);
 long long a[n];
 for(int i=0;i<n;i++)
  scanf("%lld",&a[i]);
 for(int i=0;i<n;i++)
  r[a[i]]++;
 for(int i=0;i<n;i++)
 {
  r[a[i]]--;
  if(a[i]%k==0)
  {
   ans+=l[a[i]/k]*r[a[i]*k];
  }
  l[a[i]]++;
 }
 printf("%lld\n",ans);
 return 0;
}

Problem Tester's code:

map<long, vector<long> >m;
long solve(vector<long> A, long r) {

    int n=A.size();
    
    //hashed list of indices for every value in the array
    for(int i=0;i<n;++i)
        m[A[i]].push_back(i);
    
    long c=0,x;
    for(int i=1;i<n-1;++i)
    {
     //if A[i] is not divisible be r then no need to further proceed
        if(A[i]%r)
            continue;
        
        //Count of elements occur before A[i] and has a value of A[i]/r
        long less = upper_bound(m[A[i]/r].begin(),m[A[i]/r].end(),i-1)-m[A[i]/r].begin();
        
        //Count of elements occur after A[i] and has a value of A[i]*r
        long high = m[A[i]*r].end() - lower_bound(m[A[i]*r].begin(),m[A[i]*r].end(),i+1);
        
        //add the count of total possible combinations of both type of elements describe above
        c+=(high*less);
    }
    return c;

}