# Count number of triplets with product equal to given number

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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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); ` `    ``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

 ` `

Output:

```3
```

Time Complexity: O(n3)

An Efficient Method is to use Hashing.

1. Store all the elements in a hash_map with their index.
2. 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.
3. Return count.

## C++

 `// C++ program to count triplets with given ` `// product m ` `#include ` `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); ` `    ``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 occ = ``new` `HashMap(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.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Hash Arrays Hash

code

load comments