2 Sum Problem: Number of pairs with a given sum

Reading time: 25 minutes | Coding time: 5 minutes

In this article at OpenGenus, we will find out how we can count the number of pairs in an array whose sum is equal to a certain number. Brute force approaches will take O(N^2) time but we can solve this in O(N) time using a Hash Map. This problem is known as 2 Sum Problem.

A popular variant of this problem is to check if any pair exists with the given sum.

We solve this problem using two approaches:

• Brute force approach [ O(N^2) time and O(1) space ]
• Efficient approach using Hash Map [ O(N) time and O(N) space ]

For example:

a[] = {1,2,3,4,5,6}

sum = 5

so the pairs with sum 5 are:

{1,4}  {2,3} 

so the output is equal to 2.

Note other pairs like (1,2) (3,4) and others do not sum upto 5 so these pairs are not considered. In fact, there are 15 pairs in total.

Now to solve this problem we can take help of an efficient algorithm and use an good container data structure. But first we shall see the naive algorithm, and further solve it in a efficient approach.

Brute force

In this method we scan each and every element in the array and using the nested loop we find if any other element in the array makes the required sum in the array.

Pseudocode:

• Find all pairs
• for each pair, check if the sum is equal to given number

int count_pairs(int list, int sum)
{
    int length = length_of(list);
    int count = 0;
    
    for(int i = 0; i<length; i++)
        for(int j = i+1; j<length; j++)
            if(list[i] + list[j] == sum)
                ++count;
     return count;
}

Code implementation:

Following is the complete C++ implementation:

#include <bits/stdc++.h> 
using namespace std; 
 
int pair_calc(int arr[], int n, int sum) 
{ 
    int count = 0; 
    for (int i=0; i<n; i++) 
        for (int j=i+1; j<n; j++) 
            if (arr[i]+arr[j] == sum) 
                count++; 
  
    return count; 
} 
int main() 
{   int n;
    int a[100];
    cout<<"enter the size of array"<<endl;
    cin>>n;
    cout<<"enter the array"<<endl;
    for(int i=0;i<n;i++)
    {
    cin>>a[i];
    }
    
    int sum;
    cout<<"enter the sum:"<<endl;
    cin>>sum;
    cout << "The number of pairs= " 
         << pair_calc(a, n, sum); 
    return 0; 
} 

Output

input:
enter the size of the array:
5

enter the array:
1
3
2
4
2

enter the sum:
4

The number of pairs=2

Complexity of Brute Force approach

Time complexity: O(N^2)
Space complexity: O(1)

Efficient algorithm O(N)

We use an unordered_map to fulfill our task. This algorithm consists of two simple traversals:

1. The first traversal stores the frequency of each element in the array, in the map.
2. The second traversal actually searches the pairs that have the required sum.But in any case the pair is counted two times so the counter's value has to be halved.

And if in case the pair a[i] and a[i] satisfies the case then we will have to subtract 1 from the frequency counter.

Pseudocode:

int pairs(int a[], int sum) 
{ 
    int length = length_of(a);
    hashmap m;
    for (int i=0; i<length; i++) 
        if a[i] is not in m
            add a[i] to m with value 1 (a[i], 1)
        else
            increment value of a[i] (a[i], value++)

	int count = 0; 
	for (int i=0; i<length; i++) 
	{ 
        if(sum - a[i] is in m)
            count = count + value of sum-a[i]
		if (sum-a[i] == a[i]) 
			count--;  // to ignore duplicates
	} 

	return count/2; // as all pair has been counted twice
}

Code implementation:

Following is the complete C++ implementation:

#include <bits/stdc++.h> 
using namespace std; 
int Pairs_calc(int a[], int n, int sum) 
{ 
	unordered_map<int, int> m; 
	for (int i=0; i<n; i++) 
		m[a[i]]++; 

	int count = 0; 
	for (int i=0; i<n; i++) 
	{ 
		count += m[sum-a[i]]; 
		if (sum-a[i] == a[i]) 
			count--; 
	} 

	return count/2; 
} 
int main() 
{ 
	int arr[] = {2,4,5,1,0} ; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int sum = 6; 
	cout << "the number of pairs are = "
		<< Pairs_calc(arr, n, sum); 
	return 0; 
} 

Output:

the number of pairs are = 2

Explanation:

now in the array:
2,4,5,1,0

we wanna find the sum = 6

so the map first stores the value and its frequency of each number, here each element is unique so each has a frequency of 1.

so after this the search for the pairs begins, here the target sum is 6 so we actually search 6-a[i] for the pair.
now if we get the value of 6-a[i] in any bucket of the map,we increase the counter. But by doing so we actually increase the pair counter double times. So we need to half the value.

Complexity:

Time complexity: O(N)
Space complexity: O(N)

Note that the space complexity increases from O(1) in the brute force approach to O(N) in the efficient hashmap approach but the time complexity improves from O(N^2) to O(N) in the efficient hash map approach.

The idea is that if we compromise the space complexity, we can actually improve the time complexity.

Task

How will you modify the above efficient approach to print the pairs?

The idea is to simply print the value whenever you are incrementing the count value. To avoid duplicates, one can store the pairs in a set and at the end, print all values in the set.

With this, you have the complete knowledge of solving this problem efficiently. Enjoy.