Count pairs whose products exist in array

Introduction

In this article, we are going to learn how to write a program to count pairs whose products exist in an array. 

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

A hash table is one of the data structures used to store information. The information is composed mostly of keys and values. The effectiveness of the hash function used for mapping determines how efficient the mapping process is.

Problem Statement

The problem statement is that we are given an array of ‘n’ elements, and we have to count the number of pairs in the array whose products exist in the array.

Sample Input

Sample Output:

Explanation: 

We can solve this by simply generating all the pairs of the given array and check if the product exists or not.If it exists, then the count will be incremented and then finally return the count.

But the time complexity becomes O(n³) if we try this approach to solve this problem.

So, we can use ‘hash’ to store all the elements of the array. Then generate all the possible pairs of the given array. After that, we will check if the product of each pair is present in the ‘hash’ or not. If it exists, then increment the count. Then in the end, return the count.

Algorithm

1. Create a function for ‘countingPairs’ that will help us count the pairs.
2. We will create a hash that will be used to store the elements of the array.
3. Now, we will create all the possible pairs of the given ‘arr.’
4. Check the product of each pair is in ‘hash.’
5. If the product exists, increment the count by 1.
6. Finally, we will return the count.

Let's understand this using an example:

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

2. Calling countPairs(arr, size) using arr, array size as arguments.
3. Create an empty hashmap ‘Hash’.
4. Insert all elements of the array into ‘Hash’.

5. Now, generate all the pairs and find the product.

int product = arr[i] * arr[j]

6. Then we will check whether the product exist in the “Hash”.

                               Hash.contains(product)

7. If the product exists in the “Hash”, we will increment the result.
8. Then we will return the result.

Implementation in Java:

import java.util.*;

class CodingNinjas {

    /* 
      This function returns the count of pairs whose product exists in the array arr[].
    */
    static int countingPairs(int arr[], int n) {
        int result = 0;
 
        /* Let's create an empty hash-set which will store all the elements of the array.
        */
        HashSet< Integer> Hash = new HashSet<>();
 
        /* 
          Now, insert all the elements of the array into a set.
        */
        for (int i=0; i<n; i++)
        {
            Hash.add(arr[i]);
        }
 
        /* 
           Now, generate all the pairs and check if it exists in the 'Hash' or not.
        */
        for (int i=0; i<n; i++)
        {
            for (int j=i+1; j<n; j++)
            {
                int product = arr[i] * arr[j];
 
                /* 
                  If the product exists in the set then we will increment.
                  Count increase by 1.
                */
                if (Hash.contains(product))
                {
                    result++;
                }
            }
        }
 
        /* 
          Now return the count of pairs whose product exists in the array.
        */
        return result;
    }
 
    public static void main(String[] args)
    {
        int arr[] = {6, 4, 2, 12, 5, 3};
        int size = arr.length;
       
        System.out.println(countingPairs(arr, size));
    }
}

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;

/* 
  This function returns the count of pairs whose product exists in the array arr[].
*/
int countingPairs(int arr[] , int n)
{
    int result = 0;


    /* 
    Let's create an empty hash-set which will store all the elements of the array.
    */
    set< int > Hash;


    /*
    Now, insert all the elements of the array into a set.
    */
    for (int i = 0 ; i < n; i++)
        Hash.insert(arr[i]);


    /*
    Now, generate all the pairs and check if it exists in the 'Hash' or not.
    */
    for (int i = 0 ; i < n; i++)
    {
        for (int j = i + 1; j<n ; j++)
        {
            int product = arr[i]*arr[j];


            /* 
            If the product exists in the set then we will increment.
                         Count increase by 1.
                       */
            if (Hash.find(product) != Hash.end())
                result++;
        }
    }


    /* 
    Now return the count of pairs whose product exists in the array.
    */
    return result;
}


int main()
{
    int arr[] = {6, 4, 2, 12, 5, 3};;
    int size = sizeof(arr)/sizeof(arr[0]);
    cout << countingPairs(arr, size) ;
    return 0;
}

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

Run Code

Output:

Complexity Analysis 

Time Complexity: O(n²) ‘Under the assumption insert, find operation take O(1) Time.

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.