Tutorialspoint.dev

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



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.

  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 <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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter