Count Pairs With Given Sum

Difficulty Level Easy
Frequently asked in Accolite Amazon Factset Hike
Array Hash Math SortingViews 7544

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’.

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

  1. Initialize a variable answer=0.
  2. Run a loop for I in range 0 to n-1
    1. Run a loop for j in range i+1 to n-1;
      1. If arr[i]+arr[j] is equal to k, then increament answer by 1.
  3. 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

  1. Make a hash table which will store the count of each element in the array.
  2. Iterate the array for I in range 0 to n-1
    1. If arr[i] is equal to k-arr[i], then add (count_of(k-arr[i])-1) to the answer.
    2. If arr[i] is not equal to k-arr[i], then add (count_of(k-arr[i]) to the answer.
  3. Return answer.

Example

Hash table created for the array = {1, 2, 3, 3, 4, 1, 1} is:

Count Pairs With Given Sum

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).

References

Translate »