Imprima todos los pares en una array desordenada con la misma suma

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

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *