Find two non-overlapping pairs having same sum in an array

Given an unsorted array of integers, find two non-overlapping pairs in it having same sum.

 

For example,


Input:  { 3, 4, 7, 3, 4 }
Output: (4, 3) and (3, 4)
 

Input:  { 3, 4, 7, 4 }
Output: No non-overlapping pairs is present in the array
Note (3, 4) and (3, 4) forms overlapping pair as index of 3 is same in both pairs

 
 

The idea is to consider every pair of elements in the array one by one and insert it into a map. For each pair, we check if their sum exists in the map or not. If we have encountered the sum before, and elements involved in previous occurrence (m, n) don’t overlap with the current pair (i, j), we print the both pairs and return.

Below is C++ implementation of the program –
 

Download   Run Code

Output:

First Pair (4, 3)
Second Pair (3, 4)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz