Count Triplets


Problem Statement :


You are given an array and you need to find number of tripets of indices (i, j, k) such that the elements at those indices are in geometric progression for a given common ratio r and i < j < k . 

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 n and r, the size of arr and the common ratio.
The next line contains n space-seperated integers arr[i] . 

Constraints

  1 <= n <= 10^5
  1 <= r <= 10^9
  1 <= arr[i] <= 10^9

Output Format

Return the count of triplets that form a geometric progression.



Solution :



                        In C++ :

#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;
}