# Count Triplets Challenge

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

1 2 3 |
4 2 1 2 2 4 |

**Sample Output 0**

1 2 |
2 |

**Explanation 0**

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

**Sample Input 1**

1 2 3 |
6 3 1 3 9 9 27 81 |

**Sample Output 1**

1 2 |
6 |

**Explanation 1**

The triplets satisfying are index , , , , and .

**Solution**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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<Long> arr, long r) { long ans = 0; Long[] array = new Long[arr.size()]; Map<Long, Long> right = new HashMap<Long, Long>(); Map<Long, Long> left = new HashMap<Long, Long>(); 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(); List<Long> arr = new LinkedList<>(); for (int i = 0; i < n; i++) { arr.add(scanner.nextLong()); } System.out.println(countTriplets(arr, r)); } } |