## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Count Triplets Challenge

Sharing is caring!

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$.

For example, $arr=\left[1,4,16,64\right]$. If $r=4$, we have $\left[1,4,16\right]$ and $\left[4,16,64\right]$ at indices $(0, 1, 2)$ and $(1, 2, 3)$.

Function Description
Complete the countTriplets function in the editor below. It should return the number of triplets forming a geometric progression for a given $r$ 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\left[i\right]$.

Constraints
* $1 \le n \le 10^5$
* $1 \le r \le 10^9$
* $1 \le arr\left[i\right] \le 10^9$

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 $2$ triplets in satisfying our criteria, whose indices are $(0,1,3)$ and $(0,2,3)$

Sample Input 1

6 3
1 3 9 9 27 81


Sample Output 1

6


Explanation 1
The triplets satisfying are index $(0,1,2)$, $(0,1,3)$, $(1,2,4)$, $(1,3,4)$, $(1,4,5)$ and $(3,4,5)$.

Solution

package problems;
package problems;

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class CountTriplets {

static long countTriplets(List arr, long r) {
long ans = 0;
Long[] array = new Long[arr.size()];
Map right = new HashMap();
Map left = new HashMap();
for (int i = 0; i < arr.size(); i++) {
array[i] = arr.get(i);
right.put(array[i], 0l);
left.put(array[i], 0l);
}

for (int i = 0; i < array.length; i++) {
Long num = array[i];
right.put(num, right.get(num) + 1);
}

for (int i = 0; i < array.length; i++) {
Long num2 = array[i];
right.put(num2, right.get(num2) - 1);

if (num2 % r == 0) {
Long num1 = num2 / r;
Long num3 = num2 * r;

if (left.containsKey(num1) && right.containsKey(num3)) {
ans += (left.get(num1) * right.get(num3));
}
}

left.put(num2, left.get(num2) + 1);
}

return ans;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in_166661666700000_2.txt"));

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int r = scanner.nextInt();