Count pairs with given sum

Introduction

In this article, we will learn how to write a program to count the number of pairs of integers in the given array whose sum is equal to the ‘sum’ that is given using Hashing Method. 

Before we start with our problem, let us discuss what is a Hash Table? 

A Hash table is one of the essential data structures that uses a particular function known as a hash function which will map a given value with a key to retrieve the elements faster.

A hash table is a data-structure used to store information. The information is composed mainly of keys and values. The effectiveness of the hash function used for mapping determines how efficient the mapping process is.

No, let us right jump into the Problem Statement:

Problem Statement

The problem statement is that we are given an array of ‘n’ elements and a ‘sum’ integer; we have to count the number of pairs in the array whose sum is equal to the ‘sum’ that is given.

Sample Input

Sample Output:

Explanation: 

Algorithm

1. We will start by making a hash table that will store the count of each element of the array.
2. Then we iterate that array for 'i' in range '0' to 'n-1'.
   1. Then we will check if arr[i] is equal to 'k-arr[i]', then find (count_of(k-arr[i])-1) and add it to the result.
   2. If arr[i] is not equal to k-arr[i], then find (count_of(k-arr[i]) and add it to the result.
3. Then we will return the result.
    

Example

1.Let us take an array {1, 2, 4, 5, 6} as an input.

2. Create an empty hashmap ‘test’.

3. Insert all elements of the array into ‘Hash’ with their frequency.

4. Iterate that array for 'i' in range '0' to 'n-1'.

5. Now, we will check if arr[i] is equal to 'sum-arr[i]', 

7. Then find (count_of(sum-arr[i])-1) and add it to the result.

8. If arr[i] is not equal to sum-arr[i], then find (count_of(sum-arr[i]) and add it to the result.

9. Then we will return the result.

Implementation in Java:

import java.util.*;
public class CodingNinjas
{
  public static void main(String[] args) {
        Scanner scn= new Scanner(System.in);
        int n = scn.nextInt();
        int sum = scn.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> test = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = scn.nextInt();
            Integer j = test.get(arr[i]);
            test.put(arr[i], (j == null) ? 1 : j + 1);
        }
        int result = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == sum - arr[i])
            {
                result += (test.get(arr[i]) - 1);
            }
            else
            {
                Integer j = test.get(sum - arr[i]);
                if(j!=null)
                    result += j;
            }
        }
        result /= 2;
    System.out.println("Number of pairs with the given sum are: "+result);
  }
}

You can also try this code with Online Java Compiler

Run Code

Test Case

Input:

Output:

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, sum;
    cin >> n >> sum;
    unordered_map<int, int> test;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        test[arr[i]]++;
    }
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == sum - arr[i])
        {
            result += (test[arr[i]] - 1);
        }
        else
        {
            result += (test[sum - arr[i]]);
        }
    }
    result /= 2;
    cout << "Number of pairs with the given sum are: "<<result << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis 

Time Complexity: O(N), as we iterate over the array only once.

Space Complexity: O(N), as we are maintaining a hash table.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is a hashtable?

A Hash table is one of the essential data structures that uses a particular function which is known as a hash function that maps a given value with a key to retrieve the elements faster.

How do we store data in a hashmap?

In hashmap, data is stored in the form of the key-value pair. This means every key will have some value or data mapped to it.

What is reduced form?

The reduced form is replacing the elements in an array with 0 to n-1 according to the order of the elements means the smallest element will be 0, and the largest element will be n-1.

Why is HashMap used?

Hashmaps can be said to as the most commonly used implementation of the concept of a map. Hashmaps allow arbitrary objects to be associated with other arbitrary objects. This can be very useful for doing things like grouping or joining data together by some common attribute.

Which is better: HashMap or ArrayList?

ArrayList stores the elements only as values and maintains the indexing for every element. While HashMap stores elements with key and value pairs, that means two objects. So HashMap takes more memory comparatively.