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. We know that in C/C++, map lookup is logarithmic. But in many other languages like Java, map lookup is O(n). It also depends on the hashmap implementation.
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 <map>
#include <iterator>
using namespace std;
const int MAX = 1024*1024;
void solve(int product, vector<int> list) {
vector<int> pairs[2];
map<int, int> listMap;
sort(list.begin(), list.end());
for (int i = 0; i<list.size(); i++) {
listMap[list[i]] = 1;
}
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[0].push_back(list[i]);
pairs[1].push_back(product/list[i]);
}
}
cout<<"Pairs with product "<<product<<":"<<endl;
for (int i=0; i<pairs[0].size(); i++) {
cout<<pairs[0][i]<<" "<<pairs[1][i]<<endl;
}
}
int main() {
vector<int> integerList = { 1, 2, 5, 10, 1024};
int product = 10;
solve(product, integerList);
return 0;
}
Output
Pairs with product 10: 1 10 2 5
Here’s a working example: Solution
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
//
// Created by Himanshu on 20/08/21.
//
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iterator>
using namespace std;
const int MAX = 1024*1024;
void solve(int product, vector<int> list) {
vector<int> pairs[2];
map<int, int> listMap;
sort(list.begin(), list.end());
for (int i = 0; i<list.size(); i++) {
listMap[list[i]] = 1;
}
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[0].push_back(list[i]);
pairs[1].push_back(product/list[i]);
}
}
if (pairs[0].size() > 0) {
cout<<"Pairs with product "<<product<<":"<<endl;
for (int i=0; i<pairs[0].size(); i++) {
cout<<pairs[0][i]<<" "<<pairs[1][i]<<endl;
}
}
}
int main() {
vector<int> integerList = { 1, 2, 5, 10, 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: 1 10 2 5 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
Here’s a working example: Solution
However, for smaller N ie. a smaller number of elements in array we could use O(N2) approach.
Given N < MAX.