Find a Pair with the Given Sum in an Array

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 ² ) 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:
            target_set.add(arr[i])
            
    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.

People are also reading:

• Print all subarrays with 0 sum
• Majority Element
• Rearrange an array in maximum minimum form
• Check for pairs in an array with a particular sum
• Construct a tree from Inorder and Level order traversals
• WAP to Print Triangle Using * Character
• Find the maximum product of two integers in an array
• Diameter of a Binary Tree
• Sort an array in one swap whose two elements are swapped
• Maximum size square sub-matrices with all 1’s