Dada una array no ordenada A[]. La tarea es imprimir todos los pares únicos en la array sin clasificar con la misma suma.
Nota : Imprima el resultado en el formato que se muestra en los siguientes ejemplos.
Ejemplos:
Input: A[] = { 6, 4, 12, 10, 22, 54, 32, 42, 21, 11}
Output:
Pairs : ( 4, 12) ( 6, 10) have sum : 16
Pairs : ( 10, 22) ( 21, 11) have sum : 32
Pairs : ( 12, 21) ( 22, 11) have sum : 33
Pairs : ( 22, 21) ( 32, 11) have sum : 43
Pairs : ( 32, 21) ( 42, 11) have sum : 53
Pairs : ( 12, 42) ( 22, 32) have sum : 54
Pairs : ( 10, 54) ( 22, 42) have sum : 64
Input:A[]= { 4, 23, 65, 67, 24, 12, 86}
Output:
Pairs : ( 4, 86) ( 23, 67) have sum : 90
La idea es usar map en C++ STL para evitar pares de elementos duplicados.
- Cree un mapa con clave como par de enteros y valor como entero para almacenar todos los pares únicos de elementos y su suma correspondiente.
- Recorra la array y genere todos los pares posibles y almacene los pares y su suma correspondiente en el primer mapa.
- Cree un segundo mapa con clave como entero y valor como vector de par para almacenar una lista de todos los pares de elementos con una suma correspondiente.
- Finalmente, recorra el segundo mapa y, para una suma con más de un par, imprima todos los pares y luego la suma correspondiente en un formato como se muestra en el ejemplo anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print all pairs
// with equal sum
#include <bits/stdc++.h>
using namespace std;
// Function to print all pairs
// with equal sum
void pairWithEqualSum(int A[], int n)
{
map<int, vector<pair<int, int> > > mp;
// Insert all unique pairs and their
// corresponding sum in the map
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pair<int, int> p = make_pair(A[i], A[j]);
mp[A[i] + A[j]].push_back(p);
}
}
// Traverse the map mp, and for sum
// with more than one pair, print all pairs
// and the corresponding sum
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second.size() > 1) {
cout << "Pairs : ";
for (int i = 0; i < itr->second.size(); i++) {
cout << "( " << itr->second[i].first << ", "
<< itr->second[i].second << ") ";
}
cout << " have sum : " << itr->first << endl;
}
}
}
// Driver Code
int main()
{
int A[]
= { 6, 4, 12, 10, 22, 54, 32, 42, 21, 11, 8, 2 };
int n = sizeof(A) / sizeof(A[0]);
pairWithEqualSum(A, n);
return 0;
}
Java
// Java program to print all pairs
// with equal sum
import java.util.*;
class GFG {
static class pair {
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print all pairs
// with equal sum
static void pairWithEqualSum(int A[], int n)
{
Map<Integer, Vector<pair> > mp = new HashMap<>();
// Insert all unique pairs and their
// corresponding sum in the map
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pair p = new pair(A[i], A[j]);
Vector<pair> pp = new Vector<pair>();
if (mp.containsKey(A[i] + A[j]))
pp.addAll(mp.get(A[i] + A[j]));
pp.add(p);
mp.put(A[i] + A[j], pp);
}
}
// Traverse the map mp, and for sum
// with more than one pair, print all pairs
// and the corresponding sum
for (Map.Entry<Integer, Vector<pair> > itr :
mp.entrySet()) {
if (itr.getValue().size() > 1) {
System.out.print("Pairs : ");
for (int i = 0; i < itr.getValue().size();
i++) {
System.out.print(
"( " + itr.getValue().get(i).first
+ ", "
+ itr.getValue().get(i).second
+ ") ");
}
System.out.print(
" have sum : " + itr.getKey() + "\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 6, 4, 12, 10, 22, 54,
32, 42, 21, 11, 8, 2 };
int n = A.length;
pairWithEqualSum(A, n);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of the
# approach
# Function to print all pairs
# with equal sum
def pairWithEqualSum(A, n):
mp = {}
# Insert all unique pairs and their
# corresponding sum in the map
for i in range(n):
for j in range(i+1, n):
if A[i]+A[j] in mp:
mp[A[i]+A[j]].append((A[i], A[j]))
else:
mp[A[i]+A[j]] = [(A[i], A[j])]
# Traverse the map mp, and for sum
# with more than one pair, print all pairs
# and the corresponding sum
for itr in mp:
if len(mp[itr]) > 1:
print("Pairs : ", end="")
for i in range(0, len(mp[itr])):
print("(", mp[itr][i][0], ",",
mp[itr][i][1], ")", end=" ")
print("have sum :", itr)
# Driver Code
if __name__ == "__main__":
A = [6, 4, 12, 10, 22, 54,
32, 42, 21, 11, 8, 2]
n = len(A)
pairWithEqualSum(A, n)
C#
// C# program to print all pairs
// with equal sum
using System;
using System.Collections.Generic;
class GFG {
class pair {
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print all pairs
// with equal sum
static void pairWithEqualSum(int[] A, int n)
{
Dictionary<int, List<pair> > mp
= new Dictionary<int, List<pair> >();
// Insert all unique pairs and their
// corresponding sum in the map
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
pair p = new pair(A[i], A[j]);
List<pair> pp = new List<pair>();
if (mp.ContainsKey(A[i] + A[j]))
pp = AddAll(mp[A[i] + A[j]]);
pp.Add(p);
if (mp.ContainsKey(A[i] + A[j]))
mp[A[i] + A[j]] = pp;
else
mp.Add(A[i] + A[j], pp);
}
}
// Traverse the map mp, and for sum
// with more than one pair, print all pairs
// and the corresponding sum
foreach(KeyValuePair<int, List<pair> > itr in mp)
{
if (itr.Value.Count > 1) {
Console.Write("Pairs : ");
for (int i = 0; i < itr.Value.Count; i++) {
Console.Write(
"( " + itr.Value[i].first + ", "
+ itr.Value[i].second + ") ");
}
Console.Write(" have sum : " + itr.Key
+ "\n");
}
}
}
static List<pair> AddAll(List<pair> list)
{
List<pair> l = new List<pair>();
foreach(pair p in list) l.Add(p);
return l;
}
// Driver Code
public static void Main(String[] args)
{
int[] A = { 6, 4, 12, 10, 22, 54,
32, 42, 21, 11, 8, 2 };
int n = A.Length;
pairWithEqualSum(A, n);
}
}
// This code is contributed by Rajput-Ji
Producción
Pairs : ( 6, 4) ( 8, 2) have sum : 10 Pairs : ( 4, 8) ( 10, 2) have sum : 12 Pairs : ( 6, 8) ( 4, 10) ( 12, 2) have sum : 14 Pairs : ( 6, 10) ( 4, 12) have sum : 16 Pairs : ( 6, 12) ( 10, 8) have sum : 18 Pairs : ( 12, 11) ( 21, 2) have sum : 23 Pairs : ( 10, 22) ( 21, 11) have sum : 32 Pairs : ( 12, 21) ( 22, 11) have sum : 33 Pairs : ( 12, 22) ( 32, 2) have sum : 34 Pairs : ( 22, 21) ( 32, 11) have sum : 43 Pairs : ( 12, 32) ( 42, 2) have sum : 44 Pairs : ( 32, 21) ( 42, 11) have sum : 53 Pairs : ( 12, 42) ( 22, 32) have sum : 54 Pairs : ( 10, 54) ( 22, 42) have sum : 64
Otra implementación del mismo enfoque anterior utilizando un solo mapa.
Java
// Java program for the above approach
import java.io.*;
import java.util.HashMap;
import java.util.Map;
class GFG{
// Function to find pairs
public void findPairs(int arr[]){
Map<Integer,
Integer> map = new HashMap<Integer,
Integer>();
int sum = 0, element = 0;
// Iterate from 0 to arr.length
for(int i = 0; i < arr.length; i++)
{
// Iterate from i+1 to arr.length
for(int j = i + 1; j < arr.length; j++)
{
sum = arr[i] + arr[j];
// If sum is found in map
if(map.get(sum) != null)
{
// To find the first array
// element whose of the sum pair
element = map.get(sum);
// Print the output
System.out.println("Pairs:(" + arr[i] +
"," + arr[j] + ") (" +
element + "," +
(sum - element) +
") have sum:" + sum);
}
else
{
// Else put map[sum] = arr[i]
map.put(sum, arr[i]);
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {6, 4, 12, 10, 22, 54,
32, 42, 21, 11, 8, 2};
GFG obj = new GFG();
// Function Call
obj.findPairs(arr);
}
}
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find pairs
static void findPairs(int[] arr){
Dictionary<int,int> map = new Dictionary<int,int>();
int sum = 0, element = 0;
// Iterate from 0 to arr.length
for(int i = 0; i < arr.Length; i++)
{
// Iterate from i+1 to arr.length
for(int j = i + 1; j < arr.Length; j++)
{
sum = arr[i] + arr[j];
// If sum is found in map
if(map.ContainsKey(sum))
{
// To find the first array
// element whose of the sum pair
element = map[sum];
// Print the output
Console.WriteLine("Pairs:(" + arr[i] +
"," + arr[j] + ") (" +
element + "," +
(sum - element) +
") have sum:" + sum);
}
else
{
// Else put map[sum] = arr[i]
map[sum] = arr[i];
}
}
}
}
// Driver code
public static void Main(String[] args)
{
int[] arr = {6, 4, 12, 10, 22, 54,
32, 42, 21, 11, 8, 2};
// Function Call
findPairs(arr);
}
}
// This code is contributed by sanjoy_62.
Producción
Pairs:(4,12) (6,10) have sum:16 Pairs:(4,10) (6,8) have sum:14 Pairs:(12,2) (6,8) have sum:14 Pairs:(10,8) (6,12) have sum:18 Pairs:(10,2) (4,8) have sum:12 Pairs:(22,32) (12,42) have sum:54 Pairs:(22,42) (10,54) have sum:64 Pairs:(22,11) (12,21) have sum:33 Pairs:(32,11) (22,21) have sum:43 Pairs:(32,2) (12,22) have sum:34 Pairs:(42,11) (32,21) have sum:53 Pairs:(42,2) (12,32) have sum:44 Pairs:(21,11) (10,22) have sum:32 Pairs:(21,2) (12,11) have sum:23 Pairs:(8,2) (6,4) have sum:10
Complejidad de tiempo: O(n 2 logn), ya que se usan bucles anidados
Espacio auxiliar: O(n), ya que se usa espacio adicional de tamaño n para crear un Hashmap