Count Pairs Whose Products Exist in Array

Difficulty Level Easy
Frequently asked in Accolite Amazon BlackRock Moonfrog Labs Ola Cabs Snapchat Xome
Array HashViews 1754

In count pairs whose products exist in array problem we have given an array, count all the distinct pairs whose product value is present in the array.

Example

Input

A[]={2, 5, 6, 3, 15}

Output

Number of distinct pairs whose product exists in the array is: 2

Pairs are: (2, 3), (5, 3)

Brute force: Approach 1 for Count Pairs Whose Product Exist in Array

Iterate over all the pairs, and then check if that element exists in the array or not. If it exists, then increment the answer by 1.

Algorithm

  1. Initialize a variable ans with 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. Now, Run a loop for k in range 0 to n-1
        1. If A[i]*A[j] is equal to A[k], then increment the ans by 1 and break from the loop.
      2. Print ans.

C++ Program

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (A[i] * A[j] == A[k])
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 5, 6, 3, 15, 30};
    countPairs(A);
    return 0;
}

Number of distinct pairs whose product exists in array is: 4

JAVA Program

public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (A[i] * A[j] == A[k])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array is: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 5, 6, 3, 15, 30};
    countPairs(A);
  }
}

Number of distinct pairs whose product exists in array is: 4

Complexity Analysis for Count Pairs Whose Product Exist in Array

Time complexity: We are using three nested loops, all of size N. So the time complexity is O(N^3).

Space complexity: We are not using any extra space, so the space complexity is O(1).

Using Hashing: Approach 2 For Count Pairs Whose Product Exist in Array

Main idea

We will all the elements of the array in a hash table. After that, we will iterate over all the pairs if the product of the pairs exists in the array then increase the answer by 1. We can check if a product is present in the array or not by searching in the hash table in constant time.

Algorithm

  1. Declare a hash table.
  2. Initialize a variable ans with 0 which will store the answer.
  3. Run a loop for I in range 0 to n-1.
    1. Run a loop for j in range j+1 to n-1;
      1. If the product of A[i] and A[j] is present in the hash table, then increment the ans by 1.
    2. Print ans.

For example:

For array A[]={2, 4, 2, 4, 15, 8, 20}

The hash table will look like this:

Count Pairs Whose Products Exist in Array

C++ program

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    unordered_set<int> hash_table;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        hash_table.insert(A[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (hash_table.count(A[i] * A[j]) == 1)
            {
                ans++;
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
    return 0;
}

Number of distinct pairs whose product exists in array is: 7

JAVA Program

import java.util.*; 
public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        Set<Integer> hash_table=new HashSet<Integer>();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            hash_table.add(A[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if(hash_table.contains(A[i]*A[j])==true)
                {
                    ans++;
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array are: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
  }
}

Number of distinct pairs whose product exists in array are: 7

Complexity Analysis for Count Pairs Whose Product Exist in Array

Time complexity: We are using two nested loops, both of size N. So the time complexity is O(N^2).

Space complexity: We are maintaining a hash table for storing the elements of the array. So the space complexity is O(N).

References

Translate ยป