Print all pairs in an unsorted array with equal sum
Given an unsorted array A[]. The task is to print all unique pairs in the unsorted array with equal sum.
Note: Print the result in the format as shown in the below examples.
Examples:
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
The idea is to use map in C++ STL for avoiding duplicate pairs of elements.
- Create a map with key as pair of integer and value as integer to store all unique pairs of elements and their corresponding sum.
- Traverse the array and generate all possible pairs and store the pairs and their corresponding sum on the first map.
- Create a second map with key as integer and value as a vector of pair to store a list of all pairs of elements with a corresponding sum.
- Finally, traverse the second map, and for a sum with more than one pair, print all pairs and then the corresponding sum in a format as shown in the above example.
Below is the implementation of the above approach:
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 |
Javascript
// JavaScript program to print all pairs with equal sum // Function to print all pairs // with equal sum function pairWithEqualSum(A, n) { // Create an empty map let mp = new Map(); // Insert all unique pairs and their // corresponding sum in the map for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { let p = [A[i], A[j]]; let sum = A[i] + A[j]; if (mp.has(sum)) { let arr = mp.get(sum); arr.push(p); mp.set(sum, arr); } else { let temp = [] temp.push(p); mp.set(sum, temp); } } } // Traverse the map mp, and for sum // with more than one pair, print all pairs // and the corresponding sum for (let [key, value] of mp) { if (value.length > 1) { console.log( "Pairs: " ); for (let i = 0; i < value.length; i++) { console.log( "(" + value[i][0] + ", " + value[i][1] + ") " ); } console.log( " have sum : " + key); } } } // Driver Code let A = [6, 4, 12, 10, 22, 54, 32, 42, 21, 11, 8, 2]; let n = A.length; pairWithEqualSum(A, n); // This code is contributed by akashish__ |
Output
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
Time Complexity: O(n2log(n)), as nested loops are used
Auxiliary Space: O(n), as extra space of size n is used to create a map
Implementation: Another implementation of the same above approach using one Single map.
C++
#include <bits/stdc++.h> using namespace std; // Function to find pairs void findPairs(vector< int > arr) { map< int , int > mp; int sum = 0, element = 0; // Iterate from 0 to arr.length for ( int i = 0; i < arr.size(); i++) { // Iterate from i+1 to arr.length for ( int j = i + 1; j < arr.size(); j++) { sum = arr[i] + arr[j]; // If sum is found in mp if (mp.count(sum)) { // To find the first array // element whose of the sum pair element = mp[sum]; // Print the output cout << "Pairs:(" << arr[i] << "," << arr[j] << ") (" << element << "," << "(" << sum - element << ")" << ") have sum:" << sum << endl; } else { // Else put mp[sum] = arr[i] mp[sum] = arr[i]; } } } } int main() { vector< int > arr = { 6, 4, 12, 10, 22, 54, 32, 42, 21, 11, 8, 2 }; // function call findPairs(arr); } // This code is contributed by garg28harsh. |
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); } } |
Python3
class GFG : # Function to find pairs def findPairs( self , arr) : map = dict () sum = 0 element = 0 # Iterate from 0 to arr.length i = 0 while (i < len (arr)) : # Iterate from i+1 to arr.length j = i + 1 while (j < len (arr)) : sum = arr[i] + arr[j] # If sum is found in map if ( map .get( sum ) ! = None ) : # To find the first array # element whose of the sum pair element = map .get( sum ) # Print the output print ( "Pairs:(" + str (arr[i]) + "," + str (arr[j]) + ") (" + str (element) + "," + str (( sum - element)) + ") have sum:" + str ( sum )) else : # Else put map[sum] = arr[i] map [ sum ] = arr[i] j + = 1 i + = 1 # Driver Code @staticmethod def main( args) : arr = [ 6 , 4 , 12 , 10 , 22 , 54 , 32 , 42 , 21 , 11 , 8 , 2 ] obj = GFG() # Function Call obj.findPairs(arr) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
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. |
Javascript
// Function to find pairs function findPairs(arr) { let mp = {}; let sum = 0, element = 0; // Iterate from 0 to arr.length for (let i = 0; i < arr.length; i++) { // Iterate from i+1 to arr.length for (let j = i + 1; j < arr.length; j++) { sum = arr[i] + arr[j]; // If sum is found in mp if (mp[sum]) { // To find the first array // element whose of the sum pair element = mp[sum]; // Print the output document.write( "Pairs:(" + arr[i] + "," + arr[j] + ") (" + (element) + "," + "(" + (sum - element) + ")" + ") have sum:" + sum); } else { // Else put mp[sum] = arr[i] mp[sum] = arr[i]; } } } } let arr = [6, 4, 12, 10, 22, 54, 32, 42, 21, 11, 8, 2]; // function call findPairs(arr); |
Output
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
Complexity Analysis:
- Time Complexity: O(n2logn), as nested loops are used
- Auxiliary Space: O(n), as extra space of size n is used to create a Hashmap
Contact Us