How to find all pairs of integers in an array that have the same product?

Problem

Let given an integer vector,
vector<int> arr = {1, 2, 5, 10, 1024};

The goal is to find all the pairs from the given vector arr which have the product p, where p = 10;
Naive solution O(n2)

We could run two loops, and find all the pairs of integer from the vector arr. And then we could check, product of which pairs is p.

1
2
3
4
5
6
7
8
9
for (int i=0; i<arr.size(); i++) {
  for (int j=i+1; j<arr.size(); j++) {
 
    if ((arr[i]*arr[j]) == p) {
      cout<<arr[i]<<" "<<arr[j]<<endl;
    }
 
  }
}

But we could do better than that. We could solve this problem in O(n).

O(n) solution
  • Let’s create a hashmap of all the integers present in the vector arr.
  • Iterate over vector arr and check if (product/arr[i]) is present in the hashmap. In C++, map lookup is logarithmic. But in many other languages like Java, map lookup is O(n). However in C++, we can use unordered_set for O(1) lookup.

Time complexity of below solution is 𝑂(𝑛) for one product value where n is the number of integers in the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//
//  main.cpp
//  Same Product
//
//  Created by Himanshu on 20/08/21.
//
 
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
 
void solve(int product, vector<int> list) {
    vector<pair<int, int>> pairs;
    unordered_set<int> listMap(list.begin(), list.end());
     
    for (int i = 0; i<list.size(); i++) {
        if (product%list[i] == 0 && listMap.find((product/list[i])) != listMap.end()
            && (product/list[i]) > list[i]) {
            pairs.push_back({list[i], product/list[i]});
        }
    }
     
    if (pairs.size() > 0) {
        cout<<"Pairs with product "<<product<<":"<<endl;
        for (const auto &p: pairs) {
            cout<<p.first<<" "<<p.second<<endl;
        }
    }
     
}
  
int main() {
    vector<int> integerList = {10, 5, 1, 2, 1024};
    int product = 10;
 
    solve(product, integerList);
 
    return 0;
}

Output

Pairs with product 10:
1 10
2 5
Redefined problem

Let’s redefine the problem to: find all the products that could be found by multiplying any two integers of the given vector.

This problem could be solved in O(n*MAX), where MAX is the maximum product value ie. possible.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
//  main.cpp
//  Same Products
//
 
 
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
const int MAX = 1024*1024;
 
void solve(int product, vector<int> list) {
    vector<pair<int, int>> pairs;
    unordered_set<int> listMap(list.begin(), list.end());
     
    for (int i = 0; i<list.size(); i++) {
        if (product%list[i] == 0 && listMap.find((product/list[i])) != listMap.end()
            && (product/list[i]) > list[i]) {
            pairs.push_back({list[i], product/list[i]});
        }
    }
     
    if (pairs.size() > 0) {
        cout<<"Pairs with product "<<product<<":"<<endl;
        for (const auto &p: pairs) {
            cout<<p.first<<" "<<p.second<<endl;
        }
    }
     
}
  
int main() {
    vector<int> integerList = { 10, 2, 5, 1, 1024};
     
    for (int i=0; i<=MAX; i++) {
        solve(i, integerList);
    }
 
    return 0;
}

Output

Pairs with product 2:
1 2
Pairs with product 5:
1 5
Pairs with product 10:
2 5
1 10
Pairs with product 20:
2 10
Pairs with product 50:
5 10
Pairs with product 1024:
1 1024
Pairs with product 2048:
2 1024
Pairs with product 5120:
5 1024
Pairs with product 10240:
10 1024

However, for smaller n ie. a smaller number of elements in array we could use O(n2) approach.
Given n < MAX.

Leave a Reply

Your email address will not be published. Required fields are marked *