Given an integer array of size n, and an integer ‘K’, you need to count the number of pairs(need not to be unique) present in the array whose sum is equal to ‘K’.
Table of Contents
Example
Input:
Arr={1, 5, 7, 1}
K=6
Output:
2
Brute force solution for Count Pairs With Given Sum
Main idea
We can iterate over all the pairs of the given array, and then count the pairs whose sum is equal to K.
Algorithm
- Initialize a variable answer=0.
- Run a loop for I in range 0 to n-1
- Run a loop for j in range i+1 to n-1;
- If arr[i]+arr[j] is equal to k, then increament answer by 1.
- Run a loop for j in range i+1 to n-1;
- Return answer.
Implementation
C++ program
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]+a[j]==k){
ans++;
}
}
}
cout<<"Number of pairs with the given sum are: "<<ans;
}4 6 1 5 7 1
Number of pairs with the given sum are: 2
JAVA program
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i] = sc.nextInt();
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[i]+a[j]==k){
ans++;
}
}
}
System.out.println("Number of pairs with the given sum are: "+ans);
}
}
6 4 2 2 3 1 1 5
Number of pairs with the given sum are: 3
Complexity Analysis for Count Pairs With Given Sum
Time complexity
As we are iterating over all the pairs and there are approximately N^2 pairs, so the total time complexity is O(N^2).
Space complexity
We have not used any extra space, so space complexity is O(1).
Hashing Concept for Count Pairs With Given Sum
Main idea
We will maintain a hash table which will store the frequency of each number in the given array.
Now we will iterate over the array and add all the elements whose value is equal to k-arr[i].
But we have to check one condition:
If arr[i] is equal to k-arr[i], then we will subtract 1 from our answer because we have to find distinct pairs, so we cannot take arr[i] twice for a pair, that’s why we will subtract this case from our answer.
Algorithm
- Make a hash table which will store the count of each element in the array.
- Iterate the array for I in range 0 to n-1
- If arr[i] is equal to k-arr[i], then add (count_of(k-arr[i])-1) to the answer.
- If arr[i] is not equal to k-arr[i], then add (count_of(k-arr[i]) to the answer.
- Return answer.
Example
Hash table created for the array = {1, 2, 3, 3, 4, 1, 1} is:
Implementation
C++ program
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
unordered_map<int, int> fre;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
fre[arr[i]]++;
}
int answer = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] == k - arr[i])
{
answer += (fre[arr[i]] - 1);
}
else
{
answer += (fre[k - arr[i]]);
}
}
answer /= 2;
cout << "Number of pairs with the given sum are: "<<answer << endl;
return 0;
}6 4 1 2 2 2 3 4
Number of pairs with the given sum are: 4
JAVA program
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
Integer j = fre.get(arr[i]);
fre.put(arr[i], (j == null) ? 1 : j + 1);
}
int answer = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] == k - arr[i])
{
answer += (fre.get(arr[i]) - 1);
}
else
{
Integer j = fre.get(k - arr[i]);
if(j!=null)
answer += j;
}
}
answer /= 2;
System.out.println("Number of pairs with the given sum are: "+answer);
}
}
6 7 3 5 6 1 4 4
Number of pairs with the given sum are: 3
Complexity Analysis for Count Pairs With Given Sum
Time complexity
We iterate over the array only once, so the time complexity is O(N).
Space complexity
We are maintaining a hash table, so our space complexity is O(N).