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

Related Posts:

  1. Program to find first repeating element of an array.
  2. Program to merge two sorted arrays.
  3. Program to find missing number in an array.
  4. Program to sort if array is sorted.
  5. Program to print Alternate Elements of an Array.
  6. Program to swap kth element from beginning to kth element from end in an Array.
  7. Program to print all possible subarrays of the given array.
  8. Program to print kth smallest and kth largest element of an Array.
  9. Program to find equilibrium index of an Array.
  10. Program to find majority element of an Array.
  11. Program to find mean of the Array.
  12. Program to sort an Array of 0s and 1s.
  13. Program to Reverse an Array.
  14. Program to count number of odd numbers and even numbers in an array.
  15. Program to find absolute difference between sum of odd index elements and even index elements.
  16. Program to find smallest and largest element of the array.
  17. Program to count occurrences of a particular element in an array.
  18. Program to search an element in an Array (Linear Search).
  19. Program to Rotate Array Elements by ‘D’ positions.
  20. Program to find most frequent element in an array.

You may also like...

Leave a Reply

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