Find pairs in array whose sums already exist in array in C++

We are given an array. Our task is to find pairs in array whose sums already exist in array in C++. For example,

Input: 3 5 7 2 8 9
Output: 3 5
        5 2
        7 2
        3 2

Find pairs in array whose sums already exist in array in C++ solution

The first thought that comes to our mind after reading this question is to iterate over the array and for each element, find two other elements such that their sum is equal to the current element. This forms the basis of brute force which is explained below:

BRUTE FORCE

Approach:

  1. Iterate the loop three times.
  2. The first loop assigns each element as the sum we are looking for.
    for(int i=0;i<6;i++){ 
        int sum=arr[i];
  3. The second loop selects an element that is less than the required sum. If we select an element that is greater than the current element then it will only increase the time taken. Here, we calculate the remaining sum which we need to search for in the array in the third loop. We store the required digit in the variable left.
    for(int j=0;j<6;j++){ 
        if(arr[j]<sum){ 
            int left=sum-arr[j];
  4. For every such element found, the third loop finds the other element if present in the array. If such an element is found, we print both the pair and increase the counter. We are maintaining a counter to keep a count of the number of pairs and if the count is 0, we will get to know that no such pair exists.
    for(int k=0;k<6;k++){ 
        if(arr[k]==left){ 
    //pair found 
            cout<<arr[j]<<" "<<arr[k]<<endl; 
            cnt++;

    Code:

#include <iostream>
using namespace std;

int main() {
  int arr[6]={3,5,2,8,7,9};
    int cnt=0;
    for(int i=0;i<6;i++){
        int sum=arr[i];
        for(int j=0;j<6;j++){
            if(arr[j]<sum){
                int left=sum-arr[j];
                for(int k=0;k<6;k++){
                    if(arr[k]==left){ //pair found
                        cout<<arr[j]<<" "<<arr[k]<<endl;
                        cnt++;
                    }
                }
            }
        }
    }
    if(cnt==0){
        cout<<-1;
    }
    return 0;
}

TIME COMPLEXITY: O(n^3) where n is the size of the array.
SPACE COMPLEXITY: O(1)

The above code is very costly in terms of the time it takes. To improve the time taken, we can initially store all the values in a hashmap. Then we simply run two loops instead of three to check if the sum of the two elements so obtained exists in the map or not.

HASHING

Approach:

  1. We trade the time complexity with the space complexity.
  2. We use an unordered map to store the elements.
    unordered_map<int,int> hash; 
    int cnt=0; 
    //store the values in a map 
    for(int i=0;i<6;i++){ 
        hash[arr[i]]++; 
    }
  3. Then we run two loops to check if the sum of the pair so obtained exists in the map or not. The two loops ensure that all pairs are counted.
    for(int i=0;i<6;i++){ 
        for(int j=0;j<6;j++){ 
            int sum=arr[i]+arr[j]; 
            if(hash.find(sum)!=hash.end()){  //O(1) 
                cout<<arr[i]<<" "<<arr[j]<<endl; 
                cnt++; 
            } 
        } 
    }
  4. If it does, we print them.

Code:

#include <iostream>
#include<unordered_map>
using namespace std;

int main() {
    int arr[6]={3,5,2,8,7,9};
    unordered_map<int,int> hash;
    int cnt=0;

//store the values in a map
    for(int i=0;i<6;i++){
        hash[arr[i]]++;
    }

//Run the loop
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            int sum=arr[i]+arr[j];
            if(hash.find(sum)!=hash.end()){ //O(1)
                cout<<arr[i]<<" "<<arr[j]<<endl;
                cnt++;
            }
        }
    }
    if(cnt==0){
        cout<<-1;
    }
    return 0;
}

TIME COMPLEXITY: O(n^2) where n is the size of the array
SPACE COMPLEXITY: O(n)

READ MORE:

Find a pair with the given difference in C++
C++ program to find pair with greatest product in array

Leave a Reply

Your email address will not be published. Required fields are marked *