How to Count pairs whose products exist in array in C++

By Deepanjan Bose

Hello everyone, in this article, we will learn how to count pairs whose products exist in an array in C++. Also, given an array and we have to count pairs.

For Example:

Example 1:

Input: arr[] = {6, 2, 4, 12, 5, 3}

Output: 3

Explanation: 

6 * 2 = 12 exists in the array

2 * 3 = 6 exists in the array

4 * 3 = 12 exists in the array

So, total number of pairs whose product exist in the array = 3

Example 2:

Input: arr[] = {3, 5, 2, 4, 15, 8}

Output: 2

Explanation:

3 * 5 = 15 exists in the array

2 * 4 = 8 exists in the array

So, total number of pairs whose product exist in the array = 2

Count pairs whose products exist in array in C++

Basically there are two different approaches to solve this problem.

In the simpler one, first, we have to generate all the pairs in the array and then check the products of those pairs if they exist in the array. If the exists just increment the count and at last return.

Given below is the code implementation

// C++ program to count pairs whose product exist in array 
#include<bits/stdc++.h> 
using namespace std; 
   
int countPairs( int arr[] ,int n) 
{ 
    int res = 0; 
    for (int i = 0; i < n ; i++) 
    { 
        for (int j = i+1 ; j < n ; j++) 
        { 
            int prod = arr[i] * arr[j] ; 
  
            // run a loop and find if the product exist in the array
            for (int k = 0; k < n; k++) 
            { 
                // if product found in the array increment the count
                if (arr[k] == prod) 
                { 
                    res++; 
                    break; 
                } 
            } 
        } 
    } 
  
    //At last return the count of pairs whose product exist in the array 
    return res; 
}

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

Output:

3

Time complexity: O(n³)

The better approach is to use the hash table to store the elements in the array. First, generate all the possible pairs in the given array and then check the product of these pairs in the hash table. If found, then increase the count. At last return count.

Given below is the code implementation

int countPairs(int arr[] , int n) 
{ 
    //initialize the result as 0
    int res = 0; 

    //define an empty hash-set to store the array elements
    set< int > Hash; 
  
    // Insert all array element into set 
    for (int i = 0 ; i < n; i++) 
        Hash.insert(arr[i]); 
  
    //generate all the possible pair in the given array 
    //and then check product of these pairs in the hash-set
    for (int i = 0 ; i < n; i++) 
    { 
        for (int j = i + 1; j<n ; j++) 
        { 
            int prod = arr[i]*arr[j]; 
  
            // if product exists increase the count by 1
            if (Hash.find(prod) != Hash.end()) 
                res++; 
        } 
    } 
  
    // return count of pairs whose product exist in array 
    return res; 
} 

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

Output:

3

Time complexity: O(n²)

So that’s it for this tutorial. I hope, this article is helpful for you and you have understood the logic behind this program.

Mention below your comments, if you find any mistake in the article or to share more information related to the topic of this article.