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();
        List arr = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            arr.add(scanner.nextLong());
        }

        System.out.println(countTriplets(arr, r));
    }
}