Dada una array de enteros distintos, la tarea es encontrar dos pares (a, b) y (c, d) tales que ab = cd, donde a, b, c y d son elementos distintos.
Ejemplos:
Input : arr[] = {3, 4, 7, 1, 2, 9, 8}
Output : 4 2 and 1 8
Product of 4 and 2 is 8 and
also product of 1 and 8 is 8 .
Input : arr[] = {1, 6, 3, 9, 2, 10};
Output : 6 3 and 9 2
Una solución simple es ejecutar cuatro bucles para generar todos los cuádruples posibles del elemento de array. Por cada cuádruple (a, b, c, d), comprueba si a*b = c*d. La complejidad temporal de esta solución es O(n 4 ).
Una solución eficiente de este problema es usar hashing. Usamos el producto como clave y el par como valor en la tabla hash.
1. For i=0 to n-1
2. For j=i+1 to n-1
a) Find prod = arr[i]*arr[j]
b) If prod is not available in hash then make
H[prod] = make_pair(i, j) // H is hash table
c) If product is also available in hash
then print previous and current elements
of array
Implementación:
C++
// C++ program to find four elements a, b, c
// and d in array such that ab = cd
#include<bits/stdc++.h>
using namespace std;
// Function to find out four elements in array
// whose product is ab = cd
void findPairs(int arr[], int n)
{
bool found = false;
unordered_map<int, pair < int, int > > H;
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
// If product of pair is not in hash table,
// then store it
int prod = arr[i]*arr[j];
if (H.find(prod) == H.end())
H[prod] = make_pair(i,j);
// If product of pair is also available in
// then print current and previous pair
else
{
pair<int,int> pp = H[prod];
cout << arr[pp.first] << " " << arr[pp.second]
<< " and " << arr[i]<<" "<<arr[j]<<endl;
found = true;
}
}
}
// If no pair find then print not found
if (found == false)
cout << "No pairs Found" << endl;
}
//Driven code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = sizeof(arr)/sizeof(int);
findPairs(arr, n);
return 0;
}
Java
// Java program to find four elements a, b, c
// and d in array such that ab = cd
import java.io.*;
import java.util.*;
class GFG {
public static class pair {
int first,second;
pair(int f, int s)
{
first = f;
second = s;
}
};
// Function to find out four elements
// in array whose product is ab = cd
public static void findPairs(int arr[], int n)
{
boolean found = false;
HashMap<Integer, pair> hp =
new HashMap<Integer, pair>();
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If product of pair is not in
// hash table, then store it
int prod = arr[i] * arr[j];
if(!hp.containsKey(prod))
hp.put(prod, new pair(i,j));
// If product of pair is also
// available in then print
// current and previous pair
else
{
pair p = hp.get(prod);
System.out.println(arr[p.first]
+ " " + arr[p.second]
+ " " + "and" + " " +
arr[i] + " " + arr[j]);
found = true;
}
}
}
// If no pair find then print not found
if(found == false)
System.out.println("No pairs Found");
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = arr.length;
findPairs(arr, n);
}
}
// This code is contributed by akash1295.
Python3
# Python3 program to find four elements
# a, b, c and d in array such that ab = cd
# Function to find out four elements in array
# whose product is ab = cd
def findPairs(arr, n):
found = False
H = dict()
for i in range(n):
for j in range(i + 1, n):
# If product of pair is not in hash table,
# then store it
prod = arr[i] * arr[j]
if (prod not in H.keys()):
H[prod] = [i, j]
# If product of pair is also available in
# then print current and previous pair
else:
pp = H[prod]
print(arr[pp[0]], arr[pp[1]],
"and", arr[i], arr[j])
found = True
# If no pair find then print not found
if (found == False):
print("No pairs Found")
# Driver code
arr = [1, 2, 3, 4, 5, 6, 7, 8]
n = len(arr)
findPairs(arr, n)
# This code is contributed
# by mohit kumar
C#
// C# program to find four elements a, b, c
// and d in array such that ab = cd
using System;
using System.Collections.Generic;
class GFG
{
public class pair
{
public int first,second;
public pair(int f, int s)
{
first = f;
second = s;
}
};
// Function to find out four elements
// in array whose product is ab = cd
public static void findPairs(int[] arr, int n)
{
bool found = false;
Dictionary<int, pair> hp =
new Dictionary<int, pair>();
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If product of pair is not in
// hash table, then store it
int prod = arr[i] * arr[j];
if(!hp.ContainsKey(prod))
hp.Add(prod, new pair(i,j));
// If product of pair is also
// available in then print
// current and previous pair
else
{
pair p = hp[prod];
Console.WriteLine(arr[p.first]
+ " " + arr[p.second]
+ " " + "and" + " " +
arr[i] + " " + arr[j]);
found = true;
}
}
}
// If no pair find then print not found
if(found == false)
Console.WriteLine("No pairs Found");
}
// Driver code
public static void Main (String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6, 7, 8};
int n = arr.Length;
findPairs(arr, n);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find four elements a, b, c
// and d in array such that ab = cd
// Function to find out four elements
// in array whose product is ab = cd
function findPairs(arr,n)
{
let found = false;
let hp = new Map();
for(let i = 0; i < n; i++)
{
for(let j = i + 1; j < n; j++)
{
// If product of pair is not in
// hash table, then store it
let prod = arr[i] * arr[j];
if(!hp.has(prod))
hp.set(prod, [i,j]);
// If product of pair is also
// available in then print
// current and previous pair
else
{
let p = hp.get(prod);
document.write(arr[p[0]]
+ " " + arr[p[1]]
+ " " + "and" + " " +
arr[i] + " " + arr[j]+"<br>");
found = true;
}
}
}
// If no pair find then print not found
if(found == false)
document.write("No pairs Found");
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6, 7, 8];
let n = arr.length;
findPairs(arr, n);
// This code is contributed by unknown2108
</script>
Producción
1 6 and 2 3 1 8 and 2 4 2 6 and 3 4 3 8 and 4 6
Complejidad de tiempo: O(n 2 ) asumiendo que las operaciones de búsqueda e inserción toman O(1) tiempo.
Artículo Relacionado:
Encuentra cuatro elementos a, b, c y d en una array tal que a+b = c+d
Este artículo es una contribución de DANISH_RAZA . 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.
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