Dado un arreglo arr[] de tamaño N , la tarea es contar el número de cuádruples únicos (a, b, c, d) del arreglo tal que el producto de cualquier par de elementos del cuádruple sea igual al producto de el par de elementos restante.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 6}
Salida: 8
Explicación:
Hay 8 cuádruples en la array, es decir (2, 6, 3, 4), (2, 6, 4, 3), ( 6, 2, 3, 4), (6, 2, 4, 3), (3, 4, 2, 6), (4, 3, 2, 6), (3, 4, 6, 2), y (4, 3, 6, 2), que satisface la condición dada.
Por lo tanto, el número total de cuádruples es 8.Entrada: arr[] = {1, 2, 3, 4}
Salida: 0
Explicación: No existe ningún cuádruple que satisfaga la condición dada.
Enfoque ingenuo: el enfoque más simple es generar todos los cuádruples posibles a partir de la array dada utilizando cuatro bucles anidados para cada cuádruple único encontrado, verificar si satisface la condición dada o no. Finalmente, imprima el conteo de dichos tripletes obtenidos.
Complejidad de Tiempo: O(N 4 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . Para resolver este problema, almacene el producto de cada par distinto en el Hashmap M.
Cada cuádruple (a, b, c, d) que satisface la condición dada tiene 8 permutaciones:
Número de formas de ordenar (a, b) = 2 {(a, b), (b, a)}
Número de formas de ordenar ( c, d) = 2 {(c, d), (d, c)}
Nº de formas de ordenar (a, b) y (c, d) = 8 {(a, b, c, d), (a , b, d, c), (b, a, c, d), (b, a, d, c), (c, d, a, b), (c, d, b, a), (d , c, a, b), (d, c, b, a)}.
Por lo tanto, el número total de vías = 8.
Siga los pasos a continuación para resolver el problema:
- Inicialice res como 0 para almacenar el recuento de cuatrillizos resultantes.
- Cree un hashmap M para almacenar la frecuencia del producto de distintos pares en la array .
- Ahora, genere todos los pares distintos posibles (arr[i], arr[j]) de la array dada y haga lo siguiente:
- Almacene el producto de arr[i] y arr[j] en una variable prod .
- Agregue el valor de (8*M[prod]) a la variable res .
- Incremente la frecuencia de prod en el hashmap M en 1 .
- Después de los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// unique quadruples from an array
// that satisfies the given condition
void sameProductQuadruples(int nums[],
int N)
{
// Hashmap to store
// the product of pairs
unordered_map<int, int> umap;
// Store the count of
// required quadruples
int res = 0;
// Traverse the array arr[] and
// generate all possible pairs
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
// Store their product
int prod = nums[i] * nums[j];
// Pair(a, b) can be used to
// generate 8 unique permutations
// with another pair (c, d)
res += 8 * umap[prod];
// Increment um[prod] by 1
++umap[prod];
}
}
// Print the result
cout << res;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
sameProductQuadruples(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to count the number of
// unique quadruples from an array
// that satisfies the given condition
static void sameProductQuadruples(int[] nums,
int N)
{
// Hashmap to store
// the product of pairs
int[] umap = new int[10000];
// Store the count of
// required quadruples
int res = 0;
// Traverse the array arr[] and
// generate all possible pairs
for (int i = 0; i < N; ++i)
{
for (int j = i + 1; j < N; ++j)
{
// Store their product
int prod = nums[i] * nums[j];
// Pair(a, b) can be used to
// generate 8 unique permutations
// with another pair (c, d)
res += 8 * umap[prod];
// Increment um[prod] by 1
++umap[prod];
}
}
// Print the result
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 6 };
int N = arr.length;
sameProductQuadruples(arr, N);
}
}
// This code is contributed by code_hunt.
Python3
# Python program for the above approach
# Function to count the number of
# unique quadruples from an array
# that satisfies the given condition
def sameProductQuadruples(nums, N) :
# Hashmap to store
# the product of pairs
umap = {};
# Store the count of
# required quadruples
res = 0;
# Traverse the array arr[] and
# generate all possible pairs
for i in range(N) :
for j in range(i + 1, N) :
# Store their product
prod = nums[i] * nums[j];
if prod in umap :
# Pair(a, b) can be used to
# generate 8 unique permutations
# with another pair (c, d)
res += 8 * umap[prod];
# Increment umap[prod] by 1
umap[prod] += 1;
else:
umap[prod] = 1
# Print the result
print(res);
# Driver Code
if __name__ == "__main__" :
arr = [ 2, 3, 4, 6 ];
N = len(arr);
sameProductQuadruples(arr, N);
# This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to count the number of
// unique quadruples from an array
// that satisfies the given condition
static void sameProductQuadruples(int[] nums,
int N)
{
// Hashmap to store
// the product of pairs
int[] umap = new int[10000];
// Store the count of
// required quadruples
int res = 0;
// Traverse the array arr[] and
// generate all possible pairs
for (int i = 0; i < N; ++i)
{
for (int j = i + 1; j < N; ++j)
{
// Store their product
int prod = nums[i] * nums[j];
// Pair(a, b) can be used to
// generate 8 unique permutations
// with another pair (c, d)
res += 8 * umap[prod];
// Increment um[prod] by 1
++umap[prod];
}
}
// Print the result
Console.Write(res);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 3, 4, 6 };
int N = arr.Length;
sameProductQuadruples(arr, N);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count the number of
// unique quadruples from an array
// that satisfies the given condition
function sameProductQuadruples(nums, N) {
// Hashmap to store
// the product of pairs
var umap = new Array(10000).fill(0);
// Store the count of
// required quadruples
var res = 0;
// Traverse the array arr[] and
// generate all possible pairs
for (var i = 0; i < N; ++i) {
for (var j = i + 1; j < N; ++j) {
// Store their product
var prod = nums[i] * nums[j];
// Pair(a, b) can be used to
// generate 8 unique permutations
// with another pair (c, d)
res += 8 * umap[prod];
// Increment um[prod] by 1
++umap[prod];
}
}
// Print the result
document.write(res);
}
// Driver Code
var arr = [2, 3, 4, 6];
var N = arr.length;
sameProductQuadruples(arr, N);
</script>
8
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )