In this HackerRank Count Triplets Interview preparation kit problem solution You are given an array and you need to find a number of triplets 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.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
from collections import Counter
# Complete the countTriplets function below.
def countTriplets(arr, r):
a = Counter(arr)
b = Counter()
s = 0
for i in arr:
j = i//r
k = i*r
a[i]-=1
if b[j] and a[k] and not i%r:
s+=b[j]*a[k]
b[i]+=1
return s
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nr = input().rstrip().split()
n = int(nr[0])
r = int(nr[1])
arr = list(map(int, input().rstrip().split()))
ans = countTriplets(arr, r)
fptr.write(str(ans) + '\n')
fptr.close()
Problem solution in Java Programming.
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 Solution {
// Complete the countTriplets function below.
private static long countTriplets(List<Long> arr, long r) {
Map<Long, Long> potential = new HashMap<>();
Map<Long, Long> counter = new HashMap<>();
long count = 0;
for (int i = 0; i < arr.size(); i++) {
long a = arr.get(i);
long key = a / r;
if (counter.containsKey(key) && a % r == 0) {
count += counter.get(key);
}
if (potential.containsKey(key) && a % r == 0) {
long c = potential.get(key);
counter.put(a, counter.getOrDefault(a, 0L) + c);
}
potential.put(a, potential.getOrDefault(a, 0L) + 1); // Every number can be the start of a triplet.
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nr = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(nr[0]);
long r = Long.parseLong(nr[1]);
List<Long> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Long::parseLong)
.collect(toList());
long ans = countTriplets(arr, r);
bufferedWriter.write(String.valueOf(ans));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Problem solution in C++ programming.
#include <bits/stdc++.h>
using namespace std;
// Complete the countTriplets function below.
typedef long long ll;
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
long n,r;
cin >> n >> r;
map<int,long> mp2, mp3;
//mp2 to hold count of needed values after this one to complete
//2nd part of triplet
//mp3 to hold count of needed values to complete triplet
int val;
long long res = 0;
while(n--)
{
cin >> val;
if (mp3.count(val)) //This value completes mp3[val] triplets
res += mp3[val];
if (mp2.count(val)) //This value is valid as 2° part of mp2[val] triplets
mp3[val*r] += mp2[val];
mp2[val*r]++; //"Push-up" this value as possible triplet start
}
cout << res << endl;
return 0;
}
0 Comments