Number of pairs with given sum

Given an array of integers and an input value, this function finds the number of pairs that has the sum equal to the given value

Example

INPUT :
arr[] = {1, 3, 7, -4, 2}
X = 3

OUTPUT :
The number of pairs with given sum 3 is 2 ie, {1,2} is one pair and {7, -4 } is one pair.

Time complexity : O(n^2)

In this algorithm, we will traverse each element and check whether their is another element in the arrray which can be added such that it is equal to given sum

Algorithm1

1. Simply create two loops

2. In the outer loop select an element till the end of the array ie, i =0 to n-1, where n is size

3. In the inner loop select an element from i+1 to n-1. ie, j= i+1 to n-1

4. Now, find the sum of the two elements ie, arr[i] +arr[j]. If it is equal to the given sum then increase the count of the number of pairs.

C++ Program

#include<iostream>

using namespace std;

int numPairs(int arr[], int X, int n) //this function returns the number of the pairs with sum X
{
	int i, j, sum, count =0;		  //sum to find the sum of the pair, count to count the number of pairs
	for(i=0;i<n-1;i++)                //finding all the pairs, if the pair sum is equal to given sum x, then we consider that pair
	{
		for (j = i+1; j < n; ++j)
		{
			sum = arr[i] + arr[j];
			if(sum == X)
			{
				count++;
			}			
		}
	}	
	return count;	
}

int main()
{
	int arr[] = {1, 5, 7, -4, 2};
	int X = 3;
	int n = sizeof(arr)/sizeof(arr[0]);
	int ans = numPairs(arr,X,n);
	cout<<"The number of pairs in the array with sum "<<X<<" is "<<ans;
	return 0;
}
Try It

Time Complexity : O(n)

Algorithm

1. Create a map to store the frequency of each number

Till the end of the array

  1. For each element check if it can be combined with any other element other than itself to     get the given sum . If found increment the count by 1. ie, count = count + m[sum - arr[i]]
  2. As every pair is counted twice, divide count by 2 and return.

C++ Program

#include <bits/stdc++.h>
#include <tr1/unordered_map>

using namespace std::tr1;
using namespace std;

int numPairs(int arr[], int X, int n) //this function returns the number of the pairs with sum X
{
	unordered_map <int, int> m;    //creating a map m
	int count = 0;	

	for (int i = 0; i < n; ++i)
	{
		m[arr[i]]++;               //for all elements in array incrementing value 
	}

	for (int i = 0; i < n; ++i)
	{
		count = count + m[X - arr[i]];   //Incrementing count by 1, if the element is their in #include <array>
		if(X - arr[i]== arr[i])
		{
			count--;
		}
	}

	return count/2;		
}




int main()
{
	int arr[] = {1, 5, 7, -4, 2};
	int X = 3;
	int n = sizeof(arr)/sizeof(arr[0]);
	int ans = numPairs(arr,X,n);
	cout<<"The number of pairs in the array with sum "<<X<<" is "<<ans;
	return 0;
}
Try It


Next > < Prev
Scroll to Top