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

Posted in /  

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

Vinay Khatri
Last updated on September 28, 2022

    Problem

    Given an unsorted array of integers. The task is to find any two non-overlapping pairs whose sum is equal. Two pairs are said to be non-overlapping if all the elements of the pairs are at different indices.

    Sample Input

    [1, 7, 9, 3]

    Sample Output

    1 9
    7 3

    Explanation

    They both have sum as 10

    Approach

    The idea is to traverse the array and generate all possible pairs. This step takes O(N2) time. If a sum is found that is not already present, insert it into the map. Otherwise, check if any of the previously occurring pairs with that sum does not overlap with the current pair.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef pair<int, int> pp;
    
    void solve(int arr[], int n)
    {
    
       unordered_map<int, vector<pp> > map;
    
       for (int i = 0; i < n - 1; i++) {
           for (int j = i + 1; j < n; j++) {
    
               int sum = arr[i] + arr[j];
    
               if (map.find(sum) != map.end()) {
    
                   for (auto pair : map.find(sum)->second) {
                       int m = pair.first, n = pair.second;
    
                       if ((m != i && m != j) && (n != i && n != j)) {
                           cout << "Pair 1 (" << arr[i] << ", "
                               << arr[j] << ")\nPair 2 ("
                               << arr[m] << ", " << arr[n] << ")";
                           return;
                       }
                   }
               }
    
               map[sum].push_back({ i, j });
           }
       }
    
       cout << "No pairs present";
    }
    
    int main()
    {
       int arr[] = { 1, 9, 7, 3};
       int size = sizeof(arr) / sizeof(arr[0]);
    
       solve(arr, size);
    
       return 0;
    }

    Output

    Pair 1 (7, 3)
    Pair 2 (1, 9)

    Python Programming

    def solve(arr, nn):
      
       Map = {}
    
       for i in range(0, nn - 1):
           for j in range(i + 1, nn):
              
               Sum = arr[i] + arr[j]
    
               if Sum in Map:
    
                   for pair in Map[Sum]:
                       m, n = pair
    
    
                       if ((m != i and m != j) and
                           (n != i and n != j)):
                          
                           print("Pair 1 ({}, {})".
                               format(arr[i], arr[j]))
                           print("Pair 2 ({}, {})".
                               format(arr[m], arr[n]))
                           return
                      
               if Sum not in Map:
                   Map[Sum] = []
               Map[Sum].append((i, j))
      
       print("No pairs found")
    
    arr = [1, 9, 7, 3]
    nn = len(arr)
    
    solve(arr, nn)  

    Output

    Pair 1 (7, 3)
    Pair 2 (1, 9)

    Java Programming

    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    class Pair {
       public int x, y;
    
       Pair(int x, int y)
       {
           this.x = x;
           this.y = y;
       }
    }
    
    class Solution {
    
       public static void solve(int[] arr)
       {
    
           Map<Integer, List<Pair> > map = new HashMap<>();
    
           for (int i = 0; i < arr.length - 1; i++) {
               for (int j = i + 1; j < arr.length; j++) {
    
                   int sum = arr[i] + arr[j];
    
                   if (map.containsKey(sum)) {
    
                       for (Pair pair : map.get(sum)) {
                           int x = pair.x;
                           int y = pair.y;
                           if ((x != i && x != j) && (y != i && y != j)) {
                               System.out.println("Pair 1 (" + arr[i] + ", "
                                               + arr[j] + ")");
    
                               System.out.println("Pair 2 (" + arr[x] + ", "
                                               + arr[y] + ")");
    
                               return;
                           }
                       }
                   }
    
                   map.putIfAbsent(sum, new ArrayList<>());
                   map.get(sum).add(new Pair(i, j));
               }
           }
    
           System.out.print("No pairs present");
       }
    
       public static void main(String[] args)
       {
           int[] arr = {1, 9, 7, 3 };
    
           solve(arr);
       }
    }

    Output

    Pair 1 (7, 3)
    Pair 2 (1, 9)
    

    People are also reading:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments