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.