Given an array of positive integers (may contain duplicates), the task is to find the number of triplets whose product is equal to a given number t.
Examples:
Input: arr = [1, 31, 3, 1, 93, 3, 31, 1, 93]
t = 93
Output: 18
Input: arr = [4, 2, 4, 2, 3, 1]
t = 8
Output: 4
[(4, 2, 1), (4, 2, 1), (2, 4, 1), (4, 2, 1)]
Naive Approach: The easiest way to solve this is to compare each possible triplet with t and increment count if their product is equal to t.
Below is the implementation of above approach:
C++
// C++ program for above implementation #include<iostream>using namespace std ;int main(){ // The target value for which // we have to find the solution int target = 93 ; int arr[] = {1, 31, 3, 1, 93, 3, 31, 1, 93}; int length = sizeof(arr) / sizeof(arr[0]) ; // This variable contains the total // count of triplets found int totalCount = 0 ; // Loop from the first to the third //last integer in the list for(int i = 0 ; i < length - 2; i++) { // Check if arr[i] is a factor // of target or not. If not, // skip to the next element if (target % arr[i] == 0) { for (int j = i + 1 ; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) // can be a part of triplet whose // product is equal to the target if (target % (arr[i] * arr[j]) == 0) { // Find the remaining // element of the triplet int toFind = target / (arr[i] * arr[j]) ; for(int k = j + 1 ; k < length ; k++ ) { // If element is found. increment // the total count of the triplets if (arr[k] == toFind) { totalCount ++ ; } } } } } }cout << "Total number of triplets found : " << totalCount ; return 0 ; }// This code is contributed by ANKITRAI1 |
Java
// Java program for above implementation class GFG{public static void main(String[] args){ // The target value for which // we have to find the solution int target = 93 ; int[] arr = {1, 31, 3, 1, 93, 3, 31, 1, 93}; int length = arr.length; // This variable contains the total // count of triplets found int totalCount = 0 ; // Loop from the first to the third //last integer in the list for(int i = 0 ; i < length - 2; i++) { // Check if arr[i] is a factor // of target or not. If not, // skip to the next element if (target % arr[i] == 0) { for (int j = i + 1 ; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) // can be a part of triplet whose // product is equal to the target if (target % (arr[i] * arr[j]) == 0) { // Find the remaining // element of the triplet int toFind = target / (arr[i] * arr[j]); for(int k = j + 1 ; k < length ; k++ ) { // If element is found. increment // the total count of the triplets if (arr[k] == toFind) { totalCount ++ ; } } } } } } System.out.println("Total number of triplets found : " + totalCount);}}// This code is contributed by mits |
Python3
# Python program for above implementation# The target value for which we have# to find the solutiontarget = 93arr = [1, 31, 3, 1, 93, 3, 31, 1, 93]length = len(arr)# This variable contains the total# count of triplets foundtotalCount = 0# Loop from the first to the third# last integer in the listfor i in range(length - 2): # Check if arr[i] is a factor of target # or not. If not, skip to the next element if target % arr[i] == 0: for j in range(i + 1, length - 1): # Check if the pair (arr[i], arr[j]) can be # a part of triplet whose product is equal # to the target if target % (arr[i] * arr[j]) == 0: # Find the remaining element of the triplet toFind = target // (arr[i] * arr[j]) for k in range(j + 1, length): # If element is found. increment the # total count of the triplets if arr[k] == toFind: totalCount += 1print ('Total number of triplets found: ', totalCount) |
C#
// C# program for above implementation using System;class GFG{public static void Main(){ // The target value for which // we have to find the solution int target = 93 ; int[] arr = {1, 31, 3, 1, 93, 3, 31, 1, 93}; int length = arr.Length; // This variable contains the total // count of triplets found int totalCount = 0 ; // Loop from the first to the third //last integer in the list for(int i = 0 ; i < length - 2; i++) { // Check if arr[i] is a factor // of target or not. If not, // skip to the next element if (target % arr[i] == 0) { for (int j = i + 1 ; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) // can be a part of triplet whose // product is equal to the target if (target % (arr[i] * arr[j]) == 0) { // Find the remaining // element of the triplet int toFind = target / (arr[i] * arr[j]); for(int k = j + 1 ; k < length ; k++ ) { // If element is found. increment // the total count of the triplets if (arr[k] == toFind) { totalCount ++ ; } } } } } } Console.Write("Total number of triplets found : " + totalCount);}} |
PHP
<?php// PHP program for above implementation // The target value for which // we have to find the solution $target = 93 ;$arr = array(1, 31, 3, 1, 93, 3, 31, 1, 93);$length = sizeof($arr);// This variable contains the// total count of triplets found $totalCount = 0 ;// Loop from the first to the // third last integer in the list for($i = 0 ; $i < $length - 2; $i++){ // Check if arr[i] is a factor // of target or not. If not, // skip to the next element if ($target % $arr[$i] == 0) { for ($j = $i + 1 ; $j < $length - 1; $j++) { // Check if the pair (arr[i], arr[j]) // can be a part of triplet whose // product is equal to the target if ($target % ($arr[$i] * $arr[$j]) == 0) { // Find the remaining // element of the triplet $toFind = $target / ($arr[$i] * $arr[$j]) ; for($k = $j + 1 ; $k < $length ; $k++ ) { // If element is found. increment // the total count of the triplets if ($arr[$k] == $toFind) { $totalCount ++ ; } } } } }}echo ("Total number of triplets found : ");echo ($totalCount);// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// Javascript program for above implementation // The target value for which // we have to find the solution var target = 93;var arr = [ 1, 31, 3, 1, 93, 3, 31, 1, 93 ];var length = arr.length;// This variable contains the total // count of triplets found var totalCount = 0;// Loop from the first to the third // last integer in the list for(var i = 0; i < length - 2; i++){ // Check if arr[i] is a factor // of target or not. If not, // skip to the next element if (target % arr[i] == 0) { for(var j = i + 1; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) // can be a part of triplet whose // product is equal to the target if (target % (arr[i] * arr[j]) == 0) { // Find the remaining // element of the triplet var toFind = target / (arr[i] * arr[j]); for(var k = j + 1; k < length; k++) { // If element is found. increment // the total count of the triplets if (arr[k] == toFind) { totalCount ++; } } } } }}document.write("Total number of triplets found : " + totalCount);// This code is contributed by rutvik_56</script> |
Output:
Total number of triplets found: 18
Time Complexity: O(n3)
Auxiliary Space: O(1)
Efficient Approach:
- Remove the numbers which are not the factors of t from the array.
- Then sort the array so that we don’t have to verify the index of each number to avoid additional counting of pairs.
- Then store the number of times each number appears in a dictionary count.
- Use two loops to find the first two numbers of a valid triplet by checking if their product divides t
- Find the third number of the triplet and check if we have already seen the triplet to avoid duplicate calculations
- Count the total possible combinations of that triplet such that they occur in the same order (all pairs should follow the order (x, y, z) to avoid repetitions)
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// This function returns the total number of// combinations of the triplet (x, y, z) possible in the// given listint Combinations(int x, int y, int z, map<int, int> count){ int valx = count[x]; int valy = count[y]; int valz = count[z]; if (x == y) { if (y == z) { return (valx * (valy - 1) * (valz - 2)) / 6; } else { return ((((valy - 1) * valx) / 2) * valz); } } else if (y == z) { return valx * (((valz - 1) * valy) / 2); } else { return (valx * valy * valz); }}// Driver codeint main(){ // Value for which solution has to be found int target = 93; int ar[] = { 1, 31, 3, 1, 93, 3, 31, 1, 93 }; // length of the array int N = sizeof(ar) / sizeof(ar[0]); // Create a list of integers from arr which // contains only factors of the target // Using list comprehension vector<int> list; for (int i = 0; i < N; i++) if (ar[i] != 0 && target % ar[i] == 0) list.push_back(ar[i]); // Sort the list sort(list.begin(), list.end()); int length = list.size(); int arr[length]; // List to Array Conversion std::copy(list.begin(), list.end(), arr); // Initialize the Map with the default value map<int, int> count; set<string> tripletSeen; // Count the number of times a value is present in // the list and store it in a Map for further // use for (int val : list) count[val]++; // Used to store the total number of triplets int totalCount = 0; for (int i = 0; i < length - 2; i++) { for (int j = i + 1; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) can be // a part of triplet whose product is equal // to the target if (target % (arr[i] * arr[j]) == 0) { int toFind = target / (arr[i] * arr[j]); // This condition makes sure that a // solution is not repeated int a[] = { arr[i], arr[j], toFind }; sort(a, a + 3); string str = to_string(a[0]) + "#" + to_string(a[1]) + "#" + to_string(a[2]); if (toFind >= arr[i] && toFind >= arr[j] && (tripletSeen.find(str) == tripletSeen.end())) { tripletSeen.insert(str); totalCount += Combinations( arr[i], arr[j], toFind, count); } } } } cout << "Total number of triplets found: " << totalCount << endl;}// This code is contributed by phasing17 |
Java
// java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // This function returns the total number of // combinations of the triplet (x, y, z) possible in the // given list static int Combinations(int x, int y, int z, HashMap<Integer, Integer> count) { int valx = count.getOrDefault(x, 0); int valy = count.getOrDefault(y, 0); int valz = count.getOrDefault(z, 0); if (x == y) { if (y == z) { return (valx * (valy - 1) * (valz - 2)) / 6; } else { return ((((valy - 1) * valx) / 2) * valz); } } else if (y == z) { return valx * (((valz - 1) * valy) / 2); } else { return (valx * valy * valz); } } // Driver code public static void main(String[] args) { // Value for which solution has to be found int target = 93; int ar[] = { 1, 31, 3, 1, 93, 3, 31, 1, 93 }; // length of the array int N = ar.length; // Create a list of integers from arr which // contains only factors of the target // Using list comprehension ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < N; i++) if (ar[i] != 0 && target % ar[i] == 0) list.add(ar[i]); // Sort the list Collections.sort(list); int length = list.size(); // ArrayList to Array Conversion int[] arr = list.stream().mapToInt(i -> i).toArray(); // Initialize the Map with the default value HashMap<Integer, Integer> count = new HashMap<>(); HashSet<String> tripletSeen = new HashSet<>(); // Count the number of times a value is present in // the list and store it in a Map for further // use for (int val : list) count.put(val, count.getOrDefault(val, 0) + 1); // Used to store the total number of triplets int totalCount = 0; for (int i = 0; i < length - 2; i++) { for (int j = i + 1; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) can be // a part of triplet whose product is equal // to the target if (target % (arr[i] * arr[j]) == 0) { int toFind = target / (arr[i] * arr[j]); // This condition makes sure that a // solution is not repeated int a[] = { arr[i], arr[j], toFind }; Arrays.sort(a); String str = (a[0] + "#" + a[1] + "#" + a[2]); if (toFind >= arr[i] && toFind >= arr[j] && tripletSeen.contains(str) == false) { tripletSeen.add(str); totalCount += Combinations( arr[i], arr[j], toFind, count); } } } } System.out.println( "Total number of triplets found: " + totalCount); }}// This code is contributed by Kingash. |
Python3
# Python3 code to find the number of triplets# whose product is equal to a given number# in quadratic time# This function is used to initialize# a dictionary with a default valuefrom collections import defaultdict# Value for which solution has to be foundtarget = 93arr = [1, 31, 3, 1, 93, 3, 31, 1, 93]# Create a list of integers from arr which# contains only factors of the target# Using list comprehensionarr = [x for x in arr if x != 0 and target % x == 0]# Sort the listarr.sort()length = len(arr)# Initialize the dictionary with the default valuetripletSeen = defaultdict(lambda : False)count = defaultdict(lambda : 0)# Count the number of times a value is present in# the list and store it in a dictionary for further usefor key in arr: count[key] += 1# Used to store the total number of tripletstotalCount = 0# This function returns the total number of combinations# of the triplet (x, y, z) possible in the given listdef Combinations(x, y, z): if x == y: if y == z: return (count[x]*(count[y]-1)*(count[z]-2)) // 6 else: return ((((count[y]-1)*count[x]) // 2)*count[z]) elif y == z: return count[x]*(((count[z]-1)*count[y]) // 2) else: return (count[x] * count[y] * count[z])for i in range(length - 2): for j in range(i + 1, length - 1): # Check if the pair (arr[i], arr[j]) can be a # part of triplet whose product is equal to the target if target % (arr[i] * arr[j]) == 0: toFind = target // (arr[i] * arr[j]) # This condition makes sure that a solution is not repeated if (toFind >= arr[i] and toFind >= arr[j] and tripletSeen[(arr[i], arr[j], toFind)] == False): tripletSeen[(arr[i], arr[j], toFind)] = True totalCount += Combinations(arr[i], arr[j], toFind)print ('Total number of triplets found: ', totalCount) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static int getValue(Dictionary<int, int> dict, int val, int defaultVal) { if (dict.ContainsKey(val)) return dict[val]; return defaultVal; } // This function returns the total number of // combinations of the triplet (x, y, z) possible in the // given list static int Combinations(int x, int y, int z, Dictionary<int, int> count) { int valx = getValue(count, x, 0); int valy = getValue(count, y, 0); int valz = getValue(count, z, 0); if (x == y) { if (y == z) { return (valx * (valy - 1) * (valz - 2)) / 6; } else { return ((((valy - 1) * valx) / 2) * valz); } } else if (y == z) { return valx * (((valz - 1) * valy) / 2); } else { return (valx * valy * valz); } } // Driver code public static void Main(string[] args) { // Value for which solution has to be found int target = 93; int[] ar = { 1, 31, 3, 1, 93, 3, 31, 1, 93 }; // length of the array int N = ar.Length; // Create a list of integers from arr which // contains only factors of the target // Using list comprehension List<int> list = new List<int>(); for (int i = 0; i < N; i++) if (ar[i] != 0 && target % ar[i] == 0) list.Add(ar[i]); // Sort the list list.Sort(); int length = list.Count; // List to Array Conversion int[] arr = list.ToArray(); // Initialize the Map with the default value Dictionary<int, int> count = new Dictionary<int, int>(); HashSet<string> tripletSeen = new HashSet<string>(); // Count the number of times a value is present in // the list and store it in a Map for further // use foreach(int val in list) count[val] = getValue(count, val, 0) + 1; // Used to store the total number of triplets int totalCount = 0; for (int i = 0; i < length - 2; i++) { for (int j = i + 1; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) can be // a part of triplet whose product is equal // to the target if (target % (arr[i] * arr[j]) == 0) { int toFind = target / (arr[i] * arr[j]); // This condition makes sure that a // solution is not repeated int[] a = { arr[i], arr[j], toFind }; Array.Sort(a); string str = (a[0] + "#" + a[1] + "#" + a[2]); if (toFind >= arr[i] && toFind >= arr[j] && tripletSeen.Contains(str) == false) { tripletSeen.Add(str); totalCount += Combinations( arr[i], arr[j], toFind, count); } } } } Console.WriteLine("Total number of triplets found: " + totalCount); }}// This code is contributed by phasing17 |
Javascript
// JavaScript code to find the number of triplets// whose product is equal to a given number// in quadratic timefunction getValue(dict, val, defaultVal) { if (dict.hasOwnProperty(val)) return dict[val]; return defaultVal; }// Value for which solution has to be foundlet target = 93let arr = [1, 31, 3, 1, 93, 3, 31, 1, 93]// Create a list of integers from arr which// contains only factors of the target// Using list comprehensionlet arr1 = []for (var i = 0; i < arr.length; i++){ if (arr[i] != 0) if (target % arr[i] == 0) arr1.push(arr[i]) }arr = arr1// Sort the listarr.sort()let length = arr.length// Initialize the dictionary with the default valuelet tripletSeen = new Set();let count = {}// Count the number of times a value is present in// the list and store it in a dictionary for further usefor (var key of arr) count[key] = getValue(count, key, 0) + 1;// Used to store the total number of tripletslet totalCount = 0// This function returns the total number of combinations// of the triplet (x, y, z) possible in the given listfunction Combinations(x, y, z){ let valx = getValue(count, x, 0); let valy = getValue(count, y, 0); let valz = getValue(count, z, 0); if (x == y) { if (y == z) { return Math.floor((valx * (valy - 1) * (valz - 2)) / 6); } else { return (Math.floor(((valy - 1) * valx) / 2) * valz); } } else if (y == z) { return valx * Math.floor(((valz - 1) * valy) / 2); } else { return (valx * valy * valz); } }for (var i = 0; i < (length - 2); i++){ for (var j = i + 1; j < length - 1; j++) { // Check if the pair (arr[i], arr[j]) can be a // part of triplet whose product is equal to the target if (target % (arr[i] * arr[j]) == 0) { let toFind = Math.floor(target / (arr[i] * arr[j])) let str = (arr[i] + "#" + arr[j] + "#" + toFind); // This condition makes sure that a solution is not repeated if (toFind >= arr[i] && toFind >= arr[j] && !tripletSeen.has(str)) { tripletSeen.add(str) totalCount += Combinations(arr[i], arr[j], toFind) } } }}console.log('Total number of triplets found: ', totalCount)// This code is contributed by phasing17 |
Output:
Total number of triplets found: 18
Time Complexity: O(n2)
Auxiliary Space: O(n) as using hashmap
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More Information here to that Topic: geeksforgeeks.org/count-number-of-triplets-with-product-equal-to-given-number-with-duplicates-allowed/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/count-number-of-triplets-with-product-equal-to-given-number-with-duplicates-allowed/ […]