Find a Pair with the Given Sum in an Array

Posted in

Find a Pair with the Given Sum in an Array

Vinay Khatri
Last updated on September 21, 2022

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

    Leave a Comment on this Post

    0 Comments