Given an array of distinct integers(considering only positive numbers) and a number ‘m’, find the number of triplets with product equal to ‘m’.
Examples:
Input : arr[] = { 1, 4, 6, 2, 3, 8} m = 24 Output : 3 {1, 4, 6} {1, 3, 8} {4, 2, 3} Input : arr[] = { 0, 4, 6, 2, 3, 8} m = 18 Output : 0
Asked in : Microsoft
A Naive approach is to consider each and every triplet one by one and count if their product is equal to m.
C/C++
// C++ program to count triplets with given // product m #include <iostream> using namespace std; // Function to count such triplets int countTriplets( int arr[], int n, int m) { int count = 0; // Consider all triplets and count if // their product is equal to m for ( int i = 0; i < n - 2; i++) for ( int j = i + 1; j < n - 1; j++) for ( int k = j + 1; k < n; k++) if (arr[i] * arr[j] * arr[k] == m) count++; return count; } // Drivers code int main() { int arr[] = { 1, 4, 6, 2, 3, 8 }; int n = sizeof (arr) / sizeof (arr[0]); int m = 24; cout << countTriplets(arr, n, m); return 0; } |
Java
// Java program to count triplets with given // product m class GFG { // Method to count such triplets static int countTriplets( int arr[], int n, int m) { int count = 0 ; // Consider all triplets and count if // their product is equal to m for ( int i = 0 ; i < n - 2 ; i++) for ( int j = i + 1 ; j < n - 1 ; j++) for ( int k = j + 1 ; k < n; k++) if (arr[i] * arr[j] * arr[k] == m) count++; return count; } // Driver method public static void main(String[] args) { int arr[] = { 1 , 4 , 6 , 2 , 3 , 8 }; int m = 24 ; System.out.println(countTriplets(arr, arr.length, m)); } } |
C#
// C# program to count triplets // with given product m using System; public class GFG { // Method to count such triplets static int countTriplets( int [] arr, int n, int m) { int count = 0; // Consider all triplets and count if // their product is equal to m for ( int i = 0; i < n - 2; i++) for ( int j = i + 1; j < n - 1; j++) for ( int k = j + 1; k < n; k++) if (arr[i] * arr[j] * arr[k] == m) count++; return count; } // Driver method public static void Main() { int [] arr = { 1, 4, 6, 2, 3, 8 }; int m = 24; Console.WriteLine(countTriplets(arr, arr.Length, m)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to count triplets // with given product m // Function to count such triplets function countTriplets( $arr , $n , $m ) { $count = 0; // Consider all triplets and count if // their product is equal to m for ( $i = 0; $i < $n - 2; $i ++) for ( $j = $i + 1; $j < $n - 1; $j ++) for ( $k = $j + 1; $k < $n ; $k ++) if ( $arr [ $i ] * $arr [ $j ] * $arr [ $k ] == $m ) $count ++; return $count ; } // Driver code $arr = array (1, 4, 6, 2, 3, 8); $n = sizeof( $arr ); $m = 24; echo countTriplets( $arr , $n , $m ); // This code is contributed by jit_t. ?> |
Output:
3
Time Complexity: O(n3)
An Efficient Method is to use Hashing.
- Store all the elements in a hash_map with their index.
- Consider all pairs(i, j) and check following:
- If (arr[i]*arr[j] !=0 && (m % arr[i]*arr[j]) == 0), If yes, then search for ( m / (arr[i]*arr[j]) in the map.
- Also check m / (arr[i]*arr[j]) is not equal to arr[i] and arr[j].
- Also check that current triplet is not counted previously by using index stored in the map.
- If all the above conditions are satisfied, then increment count.
- Return count.
C++
// C++ program to count triplets with given // product m #include <bits/stdc++.h> using namespace std; // Function to count such triplets int countTriplets( int arr[], int n, int m) { // Store all the elements in a set unordered_map< int , int > occ; for ( int i = 0; i < n; i++) occ[arr[i]] = i; int count = 0; // Consider all pairs and check for a // third number so their product is equal to m for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // Check if current pair divides m or not // If yes, then search for (m / arr[i]*arr[j]) if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0)) { int check = m / (arr[i] * arr[j]); auto it = occ.find(check); // Check if the third number is present // in the map and it is not equal to any // other two elements and also check if // this triplet is not counted already // using their indexes if (check != arr[i] && check != arr[j] && it != occ.end() && it->second > i && it->second > j) count++; } } } // Return number of triplets return count; } // Drivers code int main() { int arr[] = { 1, 4, 6, 2, 3, 8 }; int n = sizeof (arr) / sizeof (arr[0]); int m = 24; cout << countTriplets(arr, n, m); return 0; } |
Java
// Java program to count triplets with given // product m import java.util.HashMap; class GFG { // Method to count such triplets static int countTriplets( int arr[], int n, int m) { // Store all the elements in a set HashMap<Integer, Integer> occ = new HashMap<Integer, Integer>(n); for ( int i = 0 ; i < n; i++) occ.put(arr[i], i); int count = 0 ; // Consider all pairs and check for a // third number so their product is equal to m for ( int i = 0 ; i < n - 1 ; i++) { for ( int j = i + 1 ; j < n; j++) { // Check if current pair divides m or not // If yes, then search for (m / arr[i]*arr[j]) if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0 ) && (m % (arr[i] * arr[j]) == 0 )) { int check = m / (arr[i] * arr[j]); occ.containsKey(check); // Check if the third number is present // in the map and it is not equal to any // other two elements and also check if // this triplet is not counted already // using their indexes if (check != arr[i] && check != arr[j] && occ.containsKey(check) && occ.get(check) > i && occ.get(check) > j) count++; } } } // Return number of triplets return count; } // Driver method public static void main(String[] args) { int arr[] = { 1 , 4 , 6 , 2 , 3 , 8 }; int m = 24 ; System.out.println(countTriplets(arr, arr.length, m)); } } |
Output:
3
Time Complexity : O(n2)
Auxiliary Space : O(n)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments