Cuente el número de trillizos con un producto igual al número dado – Part 2

Dada una array de enteros distintos (considerando solo números positivos) y un número ‘m’, encuentre el número de tripletes con un producto igual a ‘m’.

Ejemplos:  

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

Preguntado en: Microsoft

Un enfoque ingenuo es considerar todos y cada triplete uno por uno y contar si su producto es igual a m.  

Implementación:

// 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 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));
    }
}

# Python3 program to count
# triplets with given product m
 
# Method to count such triplets
def countTriplets(arr, n, m):
     
    count = 0
 
    # Consider all triplets and count if
    # their product is equal to m
    for i in range (n - 2):
        for j in range (i + 1, n - 1):
            for k in range (j + 1, n):
                if (arr[i] * arr[j] * arr[k] == m):
                    count += 1
    return count
 
# Driver code
if __name__ == "__main__":
   
    arr = [1, 4, 6, 2, 3, 8]
    m = 24
    print(countTriplets(arr,
                        len(arr), m))
 
# This code is contributed by Chitranayal

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

<script>
// Javascript program to count triplets with given
// product m
     
    // Method to count such triplets
    function countTriplets(arr,n,m)
    {
        let count = 0;
  
        // Consider all triplets and count if
        // their product is equal to m
        for (let i = 0; i < n - 2; i++)
            for (let j = i + 1; j < n - 1; j++)
                for (let k = j + 1; k < n; k++)
                    if (arr[i] * arr[j] * arr[k] == m)
                        count++;
  
        return count;
    }
     
    // Driver method
    let arr = [ 1, 4, 6, 2, 3, 8];
    let m = 24;
    document.write(countTriplets(arr, arr.length, m));
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

3

Complejidad temporal: O(n ³ )

Un método eficiente es usar Hashing.  

1. Almacene todos los elementos en un hash_map con su índice.
2. Considere todos los pares (i, j) y verifique lo siguiente: 
   • Si (arr[i]*arr[j] !=0 && (m % arr[i]*arr[j]) == 0), en caso afirmativo, busque ( m / (arr[i]*arr[ j]) en el mapa.
   • Compruebe también que m / (arr[i]*arr[j]) no es igual a arr[i] y arr[j].
   • Además, verifique que el triplete actual no se cuente previamente utilizando el índice almacenado en el mapa.
   • Si se cumplen todas las condiciones anteriores, aumente el conteo.
3. Cuenta de vuelta.

Implementación:

// 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 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));
    }
}

# Python3 program for the above approach
 
# Function to find the triplet
def countTriplets(li,product):
    flag = 0
    count = 0
     
    # Consider all pairs and check
    # for a third number so their
    # product is equal to product
    for i in range(len(li)):
         
        # Check if current pair
        # divides product or not
        # If yes, then search for
        # (product / li[i]*li[j])
        if li[i]!= 0 and product % li[i] == 0:
             
            for j in range(i+1, len(li)):
                
                # 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 li[j]!= 0 and product % (li[j]*li[i]) == 0:
                    if product // (li[j]*li[i]) in li:
                     
                        n = li.index(product//(li[j]*li[i]))
                     
                        if n > i and n > j:
                            flag = 1
                            count+=1
    print(count)
    
# Driver code
li = [  1, 4, 6, 2, 3, 8 ]
product = 24
 
# Function call
countTriplets(li,product)

// C# implementation of the above
// approach
using System;
using System.Collections.Generic;
class GFG{
     
// Method to count such triplets
static int countTriplets(int[] arr,
                         int n, int m)
{
  // Store all the elements
  // in a set
  Dictionary<int,
             int> occ = new Dictionary<int,
                                       int>(n); 
 
  for (int i = 0; i < n; i++)
    occ.Add(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[check] > i &&
            occ[check] > j)
          count++;
      }
    }
  }
 
  // Return number of triplets
  return count;
}
 
// Driver code
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 divyeshrabadiya07

<script>
 
// Javascript program to count triplets with given
// product m
 
// Function to count such triplets
function countTriplets(arr, n, m)
{
 
    // Store all the elements in a set
    var occ = new Map();
    for (var i = 0; i < n; i++)
    {
        occ.set(arr[i], i)
    }
 
    var count = 0;
 
    // Consider all pairs and check for a
    // third number so their product is equal to m
    for (var i = 0; i < n - 1; i++)
    {
        for (var 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)) {
                var check = parseInt(m / (arr[i] * arr[j]));
 
                var ff = occ.has(check);
                var ans;
                if(ff)
                    ans = occ.get(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]
                    && ff && ans > i
                    && ans > j)
                    count++;
            }
        }
    }
 
    // Return number of triplets
    return count;
}
 
// Drivers code
var arr = [1, 4, 6, 2, 3, 8];
var n = arr.length;
var m = 24;
document.write( countTriplets(arr, n, m));
 
// This code is contributed by importantly.
</script>

3

Complejidad de Tiempo : O(n ² ) 
Espacio Auxiliar : O(n)

Este artículo es una contribución de Sahil Chhabra . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.