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 solution target = 93 arr = [ 1 , 31 , 3 , 1 , 93 , 3 , 31 , 1 , 93 ] length = len (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 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 + = 1 print ( '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> |
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 list int 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 code int 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 approach import 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 value from collections import defaultdict # Value for which solution has to be found target = 93 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 comprehension arr = [x for x in arr if x ! = 0 and target % x = = 0 ] # Sort the list arr.sort() length = len (arr) # Initialize the dictionary with the default value tripletSeen = 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 use for key in arr: count[key] + = 1 # Used to store the total number of triplets totalCount = 0 # This function returns the total number of combinations # of the triplet (x, y, z) possible in the given list def 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 approach using 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 time function getValue(dict, val, defaultVal) { if (dict.hasOwnProperty(val)) return dict[val]; return defaultVal; } // Value for which solution has to be found let target = 93 let 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 comprehension let 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 list arr.sort() let length = arr.length // Initialize the dictionary with the default value let 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 use for ( var key of arr) count[key] = getValue(count, key, 0) + 1; // Used to store the total number of triplets let totalCount = 0 // This function returns the total number of combinations // of the triplet (x, y, z) possible in the given list function 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 |
Total number of triplets found: 18
Time Complexity: O(n2)
Auxiliary Space: O(n) as using hashmap
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!