# 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 (Pair in an Array with given sum):

```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 Approachto find pair in an array with given sum

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:

```/* C++ Program to find a pair in an array with given Sum */
#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 to find Pair in an array with given sum

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 pair in an array with given sum is as follows:

```/* C++ Program to find pair in an array with given Sum */
#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: