ronith
10/15/2018 - 7:28 AM

number of triplets with given product

Given an array of positive integers(may contain duplicates) and a number ‘m’, find the number of unordered triplets ((Ai, Aj, Ak) and (Aj, Ai, Ak) and other permutations are counted as one only) with product equal to ‘m’.

Examples:

Input: arr[] = { 1, 4, 6, 2, 3, 8}, M = 24 Output: 3 The triplets are {1, 4, 6} {1, 3, 8} {4, 2, 3}

Input: arr[] = { 0, 4, 6, 2, 3, 8}, M = 18 Output: 0 There are no triplets in this case

Approach:

Use a hash-map to count the frequency of every element in the given array. Declare a set which can store triplets, so that only unordered triplets are taken to count. Iterate from 1 to sqrt(m) in a loop(let variable be i), since the maximum number by which M is divisible is sqrt(M) leaving out M. Check if M is divisible by i or not and i is present in the array of integers or not, if it is, then again loop from 1 to M/i.(let the loop variable be j). Again Check if M is divisible by j or not and j is present in the array of integers or not, if it is then check if the remaining number that is ( (M / i) / j) is present or not. If it is present, then a triplet has been formed. To avoid duplicate triplets, insert them in the set in a sorted order. Check if the set the size increases after the insertion of triplet, if it does then use combinatorics to find the number of triplets. To find the number of triplets, the following conditions will be there. If all of the Ai, Aj and Ak are unique, then number of combinations will be the prthe oduct of their frequencies. If all of them are same, then we can only choose three of them, hence the formula stands at frequency \choose 3. If any of the two are same(let Ai and Aj), the count will be frequency[Ai] \choose 2 * frequency[Ak]

//https://www.geeksforgeeks.org/count-number-of-triplets-with-product-equal-to-given-number-with-duplicates-allowed-set-2/
#include <bits/stdc++.h>
using namespace std;

int func(int a[], int n, int m) {
    unordered_map <int, int> freq;

    set<pair <int, pair <int,int>>> st;

    for (int i=0;i<n;i++)
        freq[a[i]]+= 1;
    int ans=0;

    for (int i=1;i*i<=m;i++) {
        if (m%i==0 && freq[i]) {
            int num1= m/i;
            for (int j=1;j*j<num1;j++) {
                if (num1%j==0 && freq[j]) {
                    int num2= num1/j;
                    if (freq[num2]) {
                        int temp[]= {num2, i,j};
                        sort (temp, temp+3);

                        int size= st.size();
                        st.insert({temp[0], {temp[1], temp[2]}});
                        if (size!= st.size()) {
                            if (j!=i && j!= num2 && i != num2)
                                ans+= freq[i]*freq[j]*freq[num2];
                            else if (j==i && j!= num2)
                                ans+= (freq[i]* (freq[i]-1)/2)*freq[num2];
                            else if (j==i && j!=num2)
                                ans+= (freq[j]* (freq[j]-1)/2)*freq[num2];
                            else if (i==j && j==num2)
                                ans+= (freq[i]*(freq[i]-1)*(freq[i]-2))/6;
                            else
                                ans+= (freq[i]* (freq[i]-1)/2)*freq[j];
                        }
                    }
                }
            }
        }
    }
    return ans;
}


int main() {
    int n, m;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    cin>>m;

    cout<<func(a,n,m);
}