# 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:**

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

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:

- Use two nested loops for the solution.
- For every element of the array, traverse the array to check whether any other element exist which sums up to ‘x’.
- 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; }

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

**Method 2: Using Hashing**

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

- Create an empty ‘set’ of preferred data type (i.e., int).
- For every element of the array, if the (x-arr[i]) exists in the set, return true.
- 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; }

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