Dada una array, cuente los pares cuyo valor de producto está presente en la array.
Ejemplos:
Input : arr[] = {6, 2, 4, 12, 5, 3}
Output : 3
All pairs whose product exist in array
(6 , 2) (2, 3) (4, 3)
Input : arr[] = {3, 5, 2, 4, 15, 8}
Output : 2
Una solución simple es generar todos los pares de una array dada y verificar si el producto existe en la array. Si existe, entonces incremente el conteo. Finalmente devuelva la cuenta.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count pairs whose product exist in array
#include<bits/stdc++.h>
using namespace std;
// Returns count of pairs whose product exists in arr[]
int countPairs( int arr[] ,int n)
{
int result = 0;
for (int i = 0; i < n ; i++)
{
for (int j = i+1 ; j < n ; j++)
{
int product = arr[i] * arr[j] ;
// find product in an array
for (int k = 0; k < n; k++)
{
// if product found increment counter
if (arr[k] == product)
{
result++;
break;
}
}
}
}
// return Count of all pair whose product exist in array
return result;
}
//Driver program
int main()
{
int arr[] = {6 ,2 ,4 ,12 ,5 ,3} ;
int n = sizeof(arr)/sizeof(arr[0]);
cout << countPairs(arr, n);
return 0;
}
Java
// Java program to count pairs
// whose product exist in array
import java.io.*;
class GFG
{
// Returns count of pairs
// whose product exists in arr[]
static int countPairs(int arr[],
int n)
{
int result = 0;
for (int i = 0; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
int product = arr[i] * arr[j] ;
// find product
// in an array
for (int k = 0; k < n; k++)
{
// if product found
// increment counter
if (arr[k] == product)
{
result++;
break;
}
}
}
}
// return Count of all pair
// whose product exist in array
return result;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {6, 2, 4, 12, 5, 3} ;
int n = arr.length;
System.out.println(countPairs(arr, n));
}
}
// This code is contributed by anuj_67.
Python 3
# Python program to count pairs whose # product exist in array # Returns count of pairs whose # product exists in arr[] def countPairs(arr, n): result = 0; for i in range (0, n): for j in range(i + 1, n): product = arr[i] * arr[j] ; # find product in an array for k in range (0, n): # if product found increment counter if (arr[k] == product): result = result + 1; break; # return Count of all pair whose # product exist in array return result; # Driver program arr = [6, 2, 4, 12, 5, 3] ; n = len(arr); print(countPairs(arr, n)); # This code is contributed # by Shivi_Aggarwal
C#
// C# program to count pairs
// whose product exist in array
using System;
class GFG
{
// Returns count of pairs
// whose product exists in arr[]
public static int countPairs(int[] arr,
int n)
{
int result = 0;
for (int i = 0; i < n ; i++)
{
for (int j = i + 1 ; j < n ; j++)
{
int product = arr[i] * arr[j];
// find product in an array
for (int k = 0; k < n; k++)
{
// if product found
// increment counter
if (arr[k] == product)
{
result++;
break;
}
}
}
}
// return Count of all pair
// whose product exist in array
return result;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {6, 2, 4, 12, 5, 3};
int n = arr.Length;
Console.WriteLine(countPairs(arr, n));
}
}
// This code is contributed by Shrikant13
PHP
<?php
// PHP program to count pairs
// whose product exist in array
// Returns count of pairs whose
// product exists in arr[]
function countPairs($arr, $n)
{
$result = 0;
for ($i = 0; $i < $n ; $i++)
{
for ($j = $i + 1 ; $j < $n ; $j++)
{
$product = $arr[$i] * $arr[$j] ;
// find product in an array
for ($k = 0; $k < $n; $k++)
{
// if product found increment counter
if ($arr[$k] == $product)
{
$result++;
break;
}
}
}
}
// return Count of all pair whose
// product exist in array
return $result;
}
// Driver Code
$arr = array(6, 2, 4, 12, 5, 3);
$n = sizeof($arr);
echo countPairs($arr, $n);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// javascript program to count pairs
// whose product exist in array
// Returns count of pairs
// whose product exists in arr
function countPairs(arr, n)
{
var result = 0;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
var product = arr[i] * arr[j];
// find product
// in an array
for (k = 0; k < n; k++)
{
// if product found
// increment counter
if (arr[k] == product)
{
result++;
break;
}
}
}
}
// return Count of all pair
// whose product exist in array
return result;
}
// Driver Code
var arr = [ 6, 2, 4, 12, 5, 3 ];
var n = arr.length;
document.write(countPairs(arr, n));
// This code is contributed by Rajput-Ji
</script>
Producción:
3
Complejidad temporal: O(n 3 )
Espacio auxiliar: O (1)
Una solución eficiente es usar ‘hash’ que almacena todos los elementos de la array. Genere todos los pares posibles de la array dada ‘arr’ y verifique que el producto de cada par esté en ‘hash’. Si existe, entonces incremente el conteo. Finalmente devuelva la cuenta.
A continuación se muestra la implementación de la idea anterior.
C++
// A hashing based C++ program to count pairs whose product
// exists in arr[]
#include<bits/stdc++.h>
using namespace std;
// Returns count of pairs whose product exists in arr[]
int countPairs(int arr[] , int n)
{
int result = 0;
// Create an empty hash-set that store all array element
set< int > Hash;
// Insert all array element into set
for (int i = 0 ; i < n; i++)
Hash.insert(arr[i]);
// Generate all pairs and check is exist in 'Hash' or not
for (int i = 0 ; i < n; i++)
{
for (int j = i + 1; j<n ; j++)
{
int product = arr[i]*arr[j];
// if product exists in set then we increment
// count by 1
if (Hash.find(product) != Hash.end())
result++;
}
}
// return count of pairs whose product exist in array
return result;
}
// Driver program
int main()
{
int arr[] = {6 ,2 ,4 ,12 ,5 ,3};
int n = sizeof(arr)/sizeof(arr[0]);
cout << countPairs(arr, n) ;
return 0;
}
Java
// A hashing based Java program to count pairs whose product
// exists in arr[]
import java.util.*;
class GFG
{
// Returns count of pairs whose product exists in arr[]
static int countPairs(int arr[], int n) {
int result = 0;
// Create an empty hash-set that store all array element
HashSet< Integer> Hash = new HashSet<>();
// Insert all array element into set
for (int i = 0; i < n; i++)
{
Hash.add(arr[i]);
}
// Generate all pairs and check is exist in 'Hash' or not
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int product = arr[i] * arr[j];
// if product exists in set then we increment
// count by 1
if (Hash.contains(product))
{
result++;
}
}
}
// return count of pairs whose product exist in array
return result;
}
// Driver program
public static void main(String[] args)
{
int arr[] = {6, 2, 4, 12, 5, 3};
int n = arr.length;
System.out.println(countPairs(arr, n));
}
}
// This code has been contributed by 29AjayKumar
Python3
# A hashing based C++ program to count # pairs whose product exists in arr[] # Returns count of pairs whose product # exists in arr[] def countPairs(arr, n): result = 0 # Create an empty hash-set that # store all array element Hash = set() # Insert all array element into set for i in range(n): Hash.add(arr[i]) # Generate all pairs and check is # exist in 'Hash' or not for i in range(n): for j in range(i + 1, n): product = arr[i] * arr[j] # if product exists in set then # we increment count by 1 if product in(Hash): result += 1 # return count of pairs whose # product exist in array return result # Driver Code if __name__ == '__main__': arr = [6, 2, 4, 12, 5, 3] n = len(arr) print(countPairs(arr, n)) # This code is contributed by # Sanjit_Prasad
C#
// A hashing based C# program to count pairs whose product
// exists in arr[]
using System;
using System.Collections.Generic;
class GFG
{
// Returns count of pairs whose product exists in arr[]
static int countPairs(int []arr, int n)
{
int result = 0;
// Create an empty hash-set that store all array element
HashSet<int> Hash = new HashSet<int>();
// Insert all array element into set
for (int i = 0; i < n; i++)
{
Hash.Add(arr[i]);
}
// Generate all pairs and check is exist in 'Hash' or not
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int product = arr[i] * arr[j];
// if product exists in set then we increment
// count by 1
if (Hash.Contains(product))
{
result++;
}
}
}
// return count of pairs whose product exist in array
return result;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {6, 2, 4, 12, 5, 3};
int n = arr.Length;
Console.WriteLine(countPairs(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// A hashing based javascript program to count pairs whose product
// exists in arr
// Returns count of pairs whose product exists in arr
function countPairs(arr , n) {
var result = 0;
// Create an empty hash-set that store all array element
var Hash = new Set();
// Insert all array element into set
for (i = 0; i < n; i++) {
Hash.add(arr[i]);
}
// Generate all pairs and check is exist in 'Hash' or not
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
var product = arr[i] * arr[j];
// if product exists in set then we increment
// count by 1
if (Hash.has(product)) {
result++;
}
}
}
// return count of pairs whose product exist in array
return result;
}
// Driver program
var arr = [ 6, 2, 4, 12, 5, 3 ];
var n = arr.length;
document.write(countPairs(arr, n));
// This code contributed by Rajput-Ji
</script>
Producción:
3
Complejidad del tiempo: O(n 2 ) ‘Bajo el supuesto insertar, encontrar la operación tomar O(1) Tiempo ‘
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA