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.
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.
//
// 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.
//
// 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.