Dada una array de enteros positivos (puede contener duplicados ), la tarea es encontrar el número de tripletes cuyo producto es igual a un número dado t .
Ejemplos :
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)]
Enfoque ingenuo: la forma más fácil de resolver esto es comparar cada triplete posible con t e incrementar el conteo si su producto es igual a t .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Total number of triplets found: 18
Complejidad del Tiempo: O( 
)
Enfoque eficiente:
- Retire los números que no son los factores de t de la array.
- Luego ordene la array para que no tengamos que verificar el índice de cada número para evitar el conteo adicional de pares.
- Luego almacene el número de veces que aparece cada número en un recuento del diccionario .
- Use dos bucles para encontrar los dos primeros números de un triplete válido comprobando si su producto divide a t
- Encuentra el tercer número del triplete y comprueba si ya hemos visto el triplete para evitar cálculos duplicados
- Cuente el total de combinaciones posibles de ese triplete de modo que ocurran en el mismo orden (todos los pares deben seguir el orden (x, y, z) para evitar repeticiones)
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)
Producción:
Total number of triplets found: 18
Complejidad del Tiempo: O( 
)
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA