# Find a Pair with the Given Sum in an Array

Posted in

Vinay Khatri
Last updated on August 11, 2024

In this tutorial, we will implement 3 different algorithms to find all the pairs with a given sum present in an array.

## Problem Statement

We have given an array ``` arr ``` and a ``` sum ``` , and we have to find all the pairs present in the array ``` arr ``` , which addition is equal to the given ``` sum ``` .

Example

```Input
arr = [2,9,7,6,4,5,3]
sum = 11

output
(2,9), (7,4), (6,5)

Input
arr = [5, 3, 2, 6, 7]
sum = 3

Output
No pair found```

### 1. Find a pair with the given sum in an array using Brute Force

Time complexity O(N 2 ) Space complexity O(1) Brute force is a straightforward technique we can use to find all the pairs present in the array for a given sum. In this algorithm, we will use the nested loop and check for every pair sum present in the array.

C++

```#include  <iostream>

using namespace std;

//function to print all the pairs
void find_pairs(int arr[], int sum, int n)
{

int count =0;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
//if pair found
if(arr[i]+arr[j]==sum)
{
cout<<"("<<arr[i]<<","<<arr[j]<<") ";
count+=1;
}
}
}
//if there is no pair
if(count==0)
{
cout<<"No Pair found";
}
}

int main()
{
// Given array
int arr[] = {2,9,7,6,4,5,3};
//Given Sum
int sum = 11;
//Size of the array
int n = sizeof(arr)/sizeof(arr[0]);

//call function
find_pairs(arr, sum,n);

return 0;
}
```
```Output
(2,9) (7,4) (6,5)```

Python

```def find_pairs(arr,s , n):
count =0

for i in range(n):
for j in range(i+1, n):
#check if the sum of pairs is equal to given sum s
if arr[i]+arr[j]==s:
print(f"({arr[i]}, {arr[j]}) ", end =" ")
count+=1

if count==0:
print("No pair found")

#given array
arr = [2,9,7,6,4,5,3]
#given sum
s = 11
#size of the array
n = len(arr)

find_pairs(arr, s, n)
```

Output

```(2, 9) (7, 4) (6, 5)

```

### 2. Find a pair with the given sum in an array using Sorting

Time complexity O(Nlog(N)) Space complexity O(1) In this algorithm, we will first sort the array in ascending order. Then maintain the search space between the left and right indices. After sorting the array, we will check if the sum of the atmost left and atmost right elements is equal to, greater than, or less than the given sum. Then, accordingly, we will increment or decrement the pointer position from the left to right index or right to left index. C++

```#include  <iostream>
#include <bits/stdc++.h>

using namespace std;

//function to print all the pairs
void find_pairs(int arr[], int sum, int n)
{

int count =0;

//Sort the arry in ascending order
sort(arr, arr + n);

//left and right pointers
int l = 0;
int r = n-1;

while(l<r)
{
//if pair found
if(arr[l]+arr[r]==sum)
{
cout<<"("<<arr[l]<<","<<arr[r]<<") "; l++; count+=1;
}
else if(arr[l]+arr[r]>sum)
{
r--;
}
else
{
l++;
}

}

//if there is no pair
if(count==0)
{
cout<<"No Pair found";
}
}

int main()
{
// Given array
int arr[] = {2,9,7,6,4,5,3};
//Given Sum
int sum = 11;
//Size of the array
int n = sizeof(arr)/sizeof(arr[0]);

//call function
find_pairs(arr, sum,n);

return 0;
}
```

Output

`(2,9) (4,7) (5,6)`

Python

```def find_pairs(arr,s , n):
count =0

arr.sort()

#left and right pointers
l=0
r= n-1
while l<r:
if arr[l]+arr[r]==s:
print(f"({arr[l]}, {arr[r]}) ", end=" ")
l+=1
count+=1
elif arr[l]+arr[r]>s:
r-=1
else:
l+=1

if count ==0:
print("No Pair found")

#given array
arr = [2,9,7,6,4,5,3]
#given sum
s = 11
#size of the array
n = len(arr)

find_pairs(arr, s, n)
```
```
```

Output

`(2, 9) (4, 7) (5, 6)`

In the above algorithm, we are using sorting with time complexity ``` O(Nlog(N)) ``` and a while loop with time complexity ``` O(N) ``` so the total time complexity of the above algorithm becomes ``` O(Nlog(N)) ``` .

### 3. Find a pair with the given sum in an array using Hashing

Time complexity O(N) We can improve the time complexity of the problem statement to the linear time complexity of N, where N is the total number of elements present in the array ``` arr ``` . In the hashing algorithm, we will use a set that will contain the unique elements. Using the algorithm, we will iterate over every element of the array ``` arr ``` and insert the difference between array elements and the given sum into the set ``` target_set ``` if the difference is unique. If the difference is already present in the set, we will print that pair.

C++

```#include  <iostream>
#include <bits/stdc++.h>

using namespace std;

//function to print all the pairs
void find_pairs(int arr[], int sum, int n)
{

int count=0;

int target;

//declare an empty set
set <int> target_set;

for(int i=0 ;i<n; i++)
{	//target value
target = sum - arr[i];

//if target value is in set
if(target_set.count(target))
{
cout<<"("<<arr[i]<<","<<target<<") ";
count+=1;
}
else
{
target_set.insert(arr[i]);
}
}

//if there is no pair
if(count==0)
{
cout<<"No Pair found";
}
}

int main()
{
// Given array
int arr[] = {2,9,7,6,4,5,3};
//Given Sum
int sum = 11;
//Size of the array
int n = sizeof(arr)/sizeof(arr[0]);

//call function
find_pairs(arr, sum,n);

return 0;
}
```

Output

`(9,2) (4,7) (5,6)`

Python

```def find_pairs(arr,s , n):
count =0
#declare an empty set
target_set = set()
for i in range(n):
#target value
target = s - arr[i]

if target in target_set:
print(f"({arr[i]}, {target})", end=" ")
count+=1
else:

if count ==0:
print("No Pair found")

#given array
arr = [2,9,7,6,4,5,3]
#given sum
s = 11
#size of the array
n = len(arr)

find_pairs(arr, s, n)
```

Output

`(9, 2) (4, 7) (5, 6)`

## Conclusion

In this tutorial, we implemented 3 different algorithms in C++ and Python to solve the problem statement " Find a pair with the given sum in an array". Although in all the implementations, we find out all the pairs present in the given array, you can also find out the single pair by returning the single value.