Dada una array de enteros arr[] de tamaño N y un entero positivo K , la tarea es contar todos los pares distintos en la array con un producto igual a K.
Ejemplos:
Entrada: arr[] = {1, 5, 3, 4, 2}, K = 3
Salida: 1
Explicación:
Solo hay un par (1, 3) con producto = K = 3.
Entrada: arr[] = { 1, 2, 16, 4, 4}, K = 16
Salida: 2
Explicación:
Hay dos pares (1, 16) y (4, 4) con producto = K = 16.
Enfoque eficiente: la idea es usar hashing .
- Inicialmente, inserte todos los elementos de la array en el hashmap . Al insertar, ignore si un elemento en particular ya está presente en el hashmap.
- Ahora, tenemos todos los elementos únicos en el hash. Entonces, para cada elemento en la array arr[i], verificamos si arr[i] / K está presente en el hashmap o no.
- Si el valor está presente, incrementamos el conteo y eliminamos ese elemento en particular del hash (para obtener los pares únicos).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count the number of pairs
// whose product is equal to K
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX 100000
// Function to count the number of pairs
// whose product is equal to K
int countPairsWithProductK(int arr[], int n, int k)
{
// Initialize the count
int count = 0;
// Initialize empty hashmap.
bool hashmap[MAX] = { false };
// Insert array elements to hashmap
for (int i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (int i = 0; i < n; i++) {
int x = arr[i];
double index = 1.0 * k / arr[i];
// Checking if the index is a whole number
// and present in the hashmap
if (index >= 0
&& ((index - (int)(index)) == 0)
&& hashmap[k / x])
count++;
hashmap[x] = false;
}
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 5, 3, 4, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << countPairsWithProductK(arr, N, K);
return 0;
}
Java
// Java program to count the number of pairs
// whose product is equal to K
class GFG
{
static int MAX = 100000;
// Function to count the number of pairs
// whose product is equal to K
static int countPairsWithProductK(int arr[], int n, int k)
{
// Initialize the count
int count = 0;
int i;
// Initialize empty hashmap.
boolean hashmap[] = new boolean[MAX];
// Insert array elements to hashmap
for (i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (i = 0; i < n; i++) {
int x = arr[i];
double index = 1.0 * k / arr[i];
// Checking if the index is a whole number
// and present in the hashmap
if (index >= 0
&& ((index - (int)(index)) == 0)
&& hashmap[k / x])
count++;
hashmap[x] = false;
}
return count;
}
// Driver code
public static void main(String []args)
{
int arr[] = { 1, 5, 3, 4, 2 };
int N = arr.length;
int K = 3;
System.out.print(countPairsWithProductK(arr, N, K));
}
}
Python3
# Python3 program to count the number of pairs # whose product is equal to K MAX = 100000; # Function to count the number of pairs # whose product is equal to K def countPairsWithProductK(arr, n, k) : # Initialize the count count = 0; # Initialize empty hashmap. hashmap = [False]*MAX ; # Insert array elements to hashmap for i in range(n) : hashmap[arr[i]] = True; for i in range(n) : x = arr[i]; index = 1.0 * k / arr[i]; # Checking if the index is a whole number # and present in the hashmap if (index >= 0 and ((index - int(index)) == 0) and hashmap[k // x]) : count += 1; hashmap[x] = False; return count; # Driver code if __name__ == "__main__" : arr = [ 1, 5, 3, 4, 2 ]; N = len(arr); K = 3; print(countPairsWithProductK(arr, N, K)); # This code is contributed by AnkitRai01
C#
// C# program to count the number of pairs
// whose product is equal to K
using System;
class GFG
{
static int MAX = 100000;
// Function to count the number of pairs
// whose product is equal to K
static int countPairsWithProductK(int []arr, int n, int k)
{
// Initialize the count
int count = 0;
int i;
// Initialize empty hashmap.
bool []hashmap = new bool[MAX];
// Insert array elements to hashmap
for (i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (i = 0; i < n; i++) {
int x = arr[i];
double index = 1.0 * k / arr[i];
// Checking if the index is a whole number
// and present in the hashmap
if (index >= 0
&& ((index - (int)(index)) == 0)
&& hashmap[k / x])
count++;
hashmap[x] = false;
}
return count;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 5, 3, 4, 2 };
int N = arr.Length;
int K = 3;
Console.Write(countPairsWithProductK(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to count the number of pairs
// whose product is equal to K
let MAX = 100000;
// Function to count the number of pairs
// whose product is equal to K
function countPairsWithProductK(arr,n,k)
{
// Initialize the count
let count = 0;
let i;
// Initialize empty hashmap.
let hashmap = new Array(MAX);
// Insert array elements to hashmap
for (i = 0; i < n; i++)
hashmap[arr[i]] = true;
for (i = 0; i < n; i++) {
let x = arr[i];
let index = 1.0 * k / arr[i];
// Checking if the index is a whole number
// and present in the hashmap
if (index >= 0
&& ((index - Math.floor(index)) == 0)
&& hashmap[k / x])
count++;
hashmap[x] = false;
}
return count;
}
// Driver code
let arr=[1, 5, 3, 4, 2];
let N = arr.length;
let K = 3;
document.write(countPairsWithProductK(arr, N, K));
// This code is contributed by rag2127
</script>
Producción:
1
Complejidad de tiempo: O(N * log(N))
Espacio Auxiliar: O(MAX)