Count all distinct pairs with product equal to K

Given an integer array and a positive integer k, count all distinct pairs with product equal to k.

Examples:

Input: arr[] = {2, 6, 4, 3, 1}, k = 12
Output: Count of pairs with the given product is 1 (2, 6) = 2 * 6 = 12 = k

Input: arr[] = {3, 5, 9, 1, 15, 3}, k = 45
Output: Count of pairs with the given product is 2 (5, 9) and (3, 15)

Method 1 (Simple):
A simple solution is to consider all pairs one by one and check Product between every pair. Following program implements the simple solution. We run two loops: the outer loop picks the first element of pair, the inner loop looks for the other element. This solution doesn’t work if there are duplicates in array as the requirement is to count only distinct pairs.

Below is the implementation of the above approach:

/* A simple program to count pairs with product k */
#include <iostream> 
using namespace std; 

int countPairsWithProdK(int arr[], int n, int k) 
{ 
    int count = 0; 
    
    // Pick all elements one by one 
    for (int i = 0; i < n; i++) 
    {     
        // See if there is a pair of this picked element 
        for (int j = i+1; j < n; j++) 
            if (arr[i] * arr[j] == k) 
                count++; 
    } 
    return count; 
} 

// Driver program to test above function 
int main() 
{ 
    int arr[] = {1, 5, 3, 4, 2}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 3; 
    cout << "Count of pairs with given product is " 
         << countPairsWithProdK(arr, n, k); 
    return 0; 
}

Output:

Count of pairs with given product is 1

Time Complexity: O(n*n)

Method 2 (Use Hashing):
We can also use hashing to achieve the average time complexity as O(n) for many cases.

1) Initialize count as 0. 
2) Insert all distinct elements of arr[] in a hash map. 
    While inserting, ignore an element if already present in the hash map. 
3) Do following for each element arr[i]. 
   a) Look for k / arr[i] in the hash map, if found then increment count. 
   b) Remove arr[i] from hash table.  

A very simple case where hashing works in O(n) time is the case where range of values is very small. For example, in the following implementation, range of numbers is assumed to be 0 to 99999. A simple hashing technique to use values as index can be used.

Below is the implementation of the above approach:

/* An efficient program to count pairs with Product k when the range 
   of numbers is small */
#include <iostream> 
#include <algorithm> 
using namespace std; 
#define MAX 100000 

int countPairsWithProductK(int arr[], int n, int k) 
{ 
    int count = 0; // Initialize count 
    
    // Initialize empty hashmap 
    bool hashmap[MAX] = {false}; 
    
    // Insert array elements into hashmap 
    for (int i = 0; i < n; i++) 
        hashmap[arr[i]] = true; 
    
    for (int i = 0; i < n; i++) 
    { 
        int x = arr[i]; 
        
        double index = 1.0 * k / arr[i]; 
        
        // Checking if index is a whole number
        if (index >= 0 && (index - (int)(index)) == 0 && hashmap[k / x]) 
            count++; 
        
        hashmap[x] = false; 
    } 
    return count; 
} 

// Driver program to test above function 
int main() 
{ 
    int arr[] = {1, 5, 3, 4, 2}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 3; 
    cout << "Count of pairs with given Product is " 
         << countPairsWithProductK(arr, n, k); 
    return 0; 
}

Output:

Count of pairs with given product is 1

Time Complexity: O(nlogn)