Dada una array de enteros distintos, encuentre si hay dos pares (a, b) y (c, d) tales que a+b = c+d, y a, b, c y d sean elementos distintos. Si hay varias respuestas, imprima cualquiera de ellas.
Ejemplo:
Input: {3, 4, 7, 1, 2, 9, 8}
Output: (3, 8) and (4, 7)
Explanation: 3+8 = 4+7
Input: {3, 4, 7, 1, 12, 9};
Output: (4, 12) and (7, 9)
Explanation: 4+12 = 7+9
Input: {65, 30, 7, 90, 1, 9, 8};
Output: No pairs found
Complejidad de tiempo esperada: O(n 2 )
Una solución simple es ejecutar cuatro bucles para generar todos los cuádruples posibles de los elementos de la 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 puede resolver este problema en tiempo O(n 2 ). La idea es usar hash . Usamos suma como clave y par como valor en la tabla hash.
Loop i = 0 to n-1 :
Loop j = i + 1 to n-1 :
calculate sum
If in hash table any index already exist
Then print (i, j) and previous pair
from hash table
Else update hash table
EndLoop;
EndLoop;
A continuación se presentan implementaciones de la idea anterior. En la implementación a continuación, se usa el mapa en lugar de un hash. La complejidad temporal de la inserción y búsqueda del mapa es en realidad O(Log n) en lugar de O(1). Entonces, debajo de la implementación está O (n 2 Log n).
C++
// Find four different elements a,b,c and d of array such that
// a+b = c+d
#include<bits/stdc++.h>
using namespace std;
bool findPairs(int arr[], int n)
{
// Create an empty Hash to store mapping from sum to
// pair indexes
map<int, pair<int, int> > Hash;
// Traverse through all possible pairs of arr[]
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
// If sum of current pair is not in hash,
// then store it and continue to next pair
int sum = arr[i] + arr[j];
if (Hash.find(sum) == Hash.end())
Hash[sum] = make_pair(i, j);
else // Else (Sum already present in hash)
{
// Find previous pair
pair<int, int> pp = Hash[sum];// pp->previous pair
// Since array elements are distinct, we don't
// need to check if any element is common among pairs
cout << "(" << arr[pp.first] << ", " << arr[pp.second]
<< ") and (" << arr[i] << ", " << arr[j] << ")n";
return true;
}
}
}
cout << "No pairs found";
return false;
}
// Driver program
int main()
{
int arr[] = {3, 4, 7, 1, 2, 9, 8};
int n = sizeof arr / sizeof arr[0];
findPairs(arr, n);
return 0;
}
Java
// Java Program to find four different elements a,b,c and d of
// array such that a+b = c+d
import java.io.*;
import java.util.*;
class ArrayElements
{
// Class to represent a pair
class pair
{
int first, second;
pair(int f,int s)
{
first = f; second = s;
}
};
boolean findPairs(int arr[])
{
// Create an empty Hash to store mapping from sum to
// pair indexes
HashMap<Integer,pair> map = new HashMap<Integer,pair>();
int n=arr.length;
// Traverse through all possible pairs of arr[]
for (int i=0; i<n; ++i)
{
for (int j=i+1; j<n; ++j)
{
// If sum of current pair is not in hash,
// then store it and continue to next pair
int sum = arr[i]+arr[j];
if (!map.containsKey(sum))
map.put(sum,new pair(i,j));
else // Else (Sum already present in hash)
{
// Find previous pair
pair p = map.get(sum);
// Since array elements are distinct, we don't
// need to check if any element is common among pairs
System.out.println("("+arr[p.first]+", "+arr[p.second]+
") and ("+arr[i]+", "+arr[j]+")");
return true;
}
}
}
return false;
}
// Testing program
public static void main(String args[])
{
int arr[] = {3, 4, 7, 1, 2, 9, 8};
ArrayElements a = new ArrayElements();
a.findPairs(arr);
}
}
// This code is contributed by Aakash Hasija
Python3
# Python Program to find four different elements a,b,c and d of
# array such that a+b = c+d
# function to find a, b, c, d such that
# (a + b) = (c + d)
def find_pair_of_sum(arr: list, n: int):
map = {}
for i in range(n):
for j in range(i+1, n):
sum = arr[i] + arr[j]
if sum in map:
print(f"{map[sum]} and ({arr[i]}, {arr[j]})")
return
else:
map[sum] = (arr[i], arr[j])
# Driver code
if __name__ == "__main__":
arr = [3, 4, 7, 1, 2, 9, 8]
n = len(arr)
find_pair_of_sum(arr, n)
C#
using System;
using System.Collections.Generic;
// C# Program to find four different elements a,b,c and d of
// array such that a+b = c+d
public class ArrayElements
{
// Class to represent a pair
public class pair
{
private readonly ArrayElements outerInstance;
public int first, second;
public pair(ArrayElements outerInstance, int f, int s)
{
this.outerInstance = outerInstance;
first = f;
second = s;
}
}
public virtual bool findPairs(int[] arr)
{
// Create an empty Hash to store mapping from sum to
// pair indexes
Dictionary<int, pair> map = new Dictionary<int, pair>();
int n = arr.Length;
// Traverse through all possible pairs of arr[]
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
// If sum of current pair is not in hash,
// then store it and continue to next pair
int sum = arr[i] + arr[j];
if (!map.ContainsKey(sum))
{
map[sum] = new pair(this, i,j);
}
else // Else (Sum already present in hash)
{
// Find previous pair
pair p = map[sum];
// Since array elements are distinct, we don't
// need to check if any element is common among pairs
Console.WriteLine("(" + arr[p.first] + ", " + arr[p.second] + ") and (" + arr[i] + ", " + arr[j] + ")");
return true;
}
}
}
return false;
}
// Testing program
public static void Main(string[] args)
{
int[] arr = new int[] {3, 4, 7, 1, 2, 9, 8};
ArrayElements a = new ArrayElements();
a.findPairs(arr);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Find four different elements a,b,c and d of array such that
// a+b = c+d
function findPairs(arr, n) {
// Create an empty Hash to store mapping from sum to
// pair indexes
let Hash = new Map();
// Traverse through all possible pairs of arr[]
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
// If sum of current pair is not in hash,
// then store it and continue to next pair
let sum = arr[i] + arr[j];
if (!Hash.has(sum))
Hash.set(sum, [i, j]);
else // Else (Sum already present in hash)
{
// Find previous pair
let pp = Hash.get(sum);// pp->previous pair
// Since array elements are distinct, we don't
// need to check if any element is common among pairs
document.write("(" + arr[pp[0]] + ", " + arr[pp[1]] + ") and (" + arr[i] + ", " + arr[j] + ")");
return true;
}
}
}
document.write("No pairs found");
return false;
}
// Driver program
let arr = [3, 4, 7, 1, 2, 9, 8];
let n = arr.length
findPairs(arr, n);
</script>
Producción:
(3, 8) and (4, 7)
Complejidad de tiempo: O (n 2 logn)
Espacio Auxiliar : O(n)
Gracias a Gaurav Ahirwar por sugerir las soluciones anteriores.
Ejercicio:
1) Extienda la solución anterior con duplicados permitidos en la array.
2) Ampliar aún más la solución para imprimir todos los cuádruples en la salida en lugar de solo uno. Y todos los cuádruples deben imprimirse en orden lexicográfico (los valores más pequeños antes que los más grandes). Supongamos que tenemos dos soluciones S1 y S2.
S1 : a1 b1 c1 d1 ( these are values of indices int the array ) S2 : a2 b2 c2 d2 S1 is lexicographically smaller than S2 iff a1 < a2 OR a1 = a2 AND b1 < b2 OR a1 = a2 AND b1 = b2 AND c1 < c2 OR a1 = a2 AND b1 = b2 AND c1 = c2 AND d1 < d2
Vea esto para la solución del ejercicio.
Este artículo es una contribución de Aarti_Rathi . 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.
Artículo relacionado:
Encuentre todos los pares (a,b) y (c,d) en una array que satisfagan ab = cd.
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