Computer Programming

How to find all 2 pairs of integers that have the same product in an array in O(n)?

Given an array arr[] of N integers, the task is to find all 2 pairs (a, b) such as: 

  • (a1* b1), (a2*b2)…. = p1
  • (a3*b3), (a4*b4)…. = p2
  • (a5*b5), (a6*b6)…. = p3 and so on..

Naive Approach

Let’s start with the naive approach first. An easiest way to do it is by using two for loops and saving product of each pair of integers in a map against product Pᵢ

//JavaScript code
function main() { 
	var integerList = [1, 2, 5, 10];
	var pairs = {}; 
	var listMap = {}; 
	integerList.sort(); 
  
  //Finding all products and saving them as keys in the map
	for (var i = 0; i<integerList.length; i++) { 
    for (var j = 0; j<i; j++) {
        listMap[integerList[i]*integerList[j]] = [];
    } 
	} 
	for (var i = 0; i<integerList.length; i++) { 
    for (var j = 0; j<i; j++) {
        var pairs = new Array;
        pairs.push(integerList[i]);
        pairs.push(integerList[j]);
        listMap[integerList[i]*integerList[j]].push(pairs);
    } 
	} 
  return listMap;
}	  
    


Now, the space and time complexity of above solution is O(n^2), where n is the number of integers in the given array.

But we could do better than that by using hashing:

function getPairs(product, list, listMap) { 
	var pairs = new Array; 
	for (var i = 0; i<list.length; i++) { 
		if (product%list[i] == 0 && (product/list[i]) in listMap && (product/list[i]) > list[i]) { 
			pairs.push([list[i], product/list[i]]); 
		} 
	}	 
	return pairs; 
} 
 
function main() { 
	var integerList = [1, 1, 2]; 
	var maxProduct = 2*1; 
	var ans = {}; 
	var listMap = {}; 
	integerList.sort(); 
	for (var i = 0; i<integerList.length; i++) { 
		listMap[integerList[i]] = 1; 
	} 
	for (var i = 1; i<=maxProduct; i++) { 
		var pairArray = getPairs(i, integerList, listMap); 
		if (pairArray.length > 0) { 
			ans[i] = pairArray; 
		} 
	} 
	return ans; 
} 
 
var solution = main(); //solution is a map & solution[i] contains all pairs with product i. 

Here we have, used the listMap as our lookup hashmap to find the other number of the product.

For a product P, time complexity of this solution would be O(n).

Also Read: https://www.aureollabs.com/n-queen-problem-analysis/