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

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(n^2)

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;
}
 

Here’s a working example:

https://ideone.com/I3HkPa

Redefined problem

Let’s redefine the problem to: find all the products which could be find 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;
}
 

Here’s a working example:

https://ideone.com/y5ZirR

However for smaller N ie. smaller number of elements in array we could use O(N^2) approach. Given N < MAX.

Leave a Reply

Your email address will not be published.