Pair in an Array with Given Sum

Pair in an Array with Given Sum” is one of the favorite technical interview problems. Here, we are given an array with ‘n’ elements and a target value ‘x’. Our task is to find a pair in an array, whose sum is equal to target value ‘x’.

Example:

INPUT:
Arr[] = {5, 7, 4, 9, 12}
sum = 16
OUTPUT:
Pair is present in array with sum as 16

There are multiple methods to find a pair in an array with given sum. Some of them are:

METHOD 1: Brute-Force Approach

The steps required to find a pair in an array with given sum is as follows:

  1. Use two nested loops for the solution.
  2. For every element of the array, traverse the array to check whether any other element exist which sums up to ‘x’.
  3. If the pair exist, return ‘Yes’, else return ‘false’.

The time complexity of this solution is O(n^2), where ‘n’ is the size of the array.

C++ Program to find a pair in an array with given sum is as follows:

#include <bits/stdc++.h>
using namespace std;
void checkSum(int arr[],int n,int sum)
{
    int i,j;
    for(i=0;i<n;i++)
    {
        int temp_sum = arr[i];
        for(j=0;j<n;j++)
        {
        // Make sure not add element with itself
            if(i!=j)
            {
                if(temp_sum + arr[j] == sum)
                {
                    cout<<"The Pair is Present in an Array with sum as "<<sum;
                    return;
                }
            }
        }
    }
    cout<<"The Pair is not Present in an Array with sum as "<<sum;
}
int main()
{
    int arr[5] = {1, 2, 4, 6, 8};
    int sum = 12;
    checkSum(arr,5,sum);
    return 0;
}

OUTPUT:
The Pair is Present in an Array with sum as 12

Method 2: Using Hashing

The steps required to find a pair in an array with given sum is as follows:

  1. Create an empty ‘set’ of  preferred data type (i.e., int).
  2. For every element of the array, if the (x-arr[i]) exists in the set, return true.
  3. Else return False.

The time complexity of this solution is O(nlogn), where ‘n’ is the size of the array and ‘logn’ for inserting and searching in set.

C++ Program to find the pair in an array with given sum is as follows:

#include <bits/stdc++.h>
using namespace std;
void checkSum(int arr[],int n,int sum)
{
    /* create a set*/
    set<int>st;
    for(int i = 0; i< n; i++)
    {
        /* Initialize temp with remaining of sum 
        after subtracting it with arr[i] */
        int temp = sum - arr[i];
        /* Check if temp is present in an array or not */
        if(st.find(temp) != st.end())
        {
            cout<<"The Pair is present in the array with sum as "<<sum;
            return;
        }
        /* If not present, insert arr[i] into set */
        st.insert(arr[i]);
    }
    cout<<"The Pair is not present in the array with sum as "<<sum;
}
int main()
{
    int arr[5] = {1, 2, 4, 6, 8};
    int sum = 12;
    checkSum(arr,5,sum);
    return 0;
}

OUTPUT:
The Pair is present in the array with sum as 12

You may also like...

Leave a Reply

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