How do I find all 2 pairs of integers that have the same product in JavaScript?

Question

I need to write a program that, when given a list of integers, it finds all 2-pairs of integers that have the same product. i.e. a 2-pair is 2 distinct pairs of integers lets say [(a,b),(c,d)] where a*b = c*d but a ≠ b ≠ c ≠ d.

The range of integers should be from 1 to 1024. What I would like to implement is that when the web page is opened the user is prompted by a pop up in which he will enter the array of integers, i.e [1,2,3,7,8,9,6] etc for instance from the input [1,2,3,7,8,9,6] the output should be [(9,2),(3,6)] since both evaluate to 18.

The coding I did so far is very basic and can be seen below. What I've done so far is the pop-up box alert the input etc, but can't seem to understand how to make the program check for the pairs and give the sum. Thanks in advance to this community who's helping me out to better understand and learn javascript!

I've done my fair bit of research below, definitely different question than mine but have gone through them.

Code:

function evaluate() {
  const input = prompt("Please enter the array of integers in the form: 1,2,3,1")
    .split(',')
    .map(item => item.trim());

  function pairs(items) {
  }

  if (input == "" || input == null) {
    document.writeln("Sorry, there is nothing that can be calculated.");
  } else {

    document.writeln("Your calculation is: ");
    document.writeln(pairs(input) + " with a starting input string of: " + input);
  }
}
evaluate()

Then what should happen in case there are multiple such cases like `[1,2,3,4,5,6,7,8]` where you can have pairs like `[[1,8],[2,4]]` and `[[3,4][2,6]]` — gurvinder372, Mar 19 '18 at 10:41

Nina Scholz · Answer 1 · 2018-03-19T10:35:41.910

You could iterate the array and a copy of the array beginning by the actual index plus one for getting the products. Store the result in an object with product as key.

Then get the keys (products) of the object, filter it to get only the results with two or more products.

var array = [1, 2, 3, 7, 8, 9, 6],
    result = {},
    pairs;
    
array.forEach(function (a, i) {
    array.slice(i + 1).forEach(function (b) {
        (result[a * b] = (result[a * b] || [])).push([a, b]);
    });
});

pairs = Object
    .keys(result)
    .filter(function (k) { return result[k].length >= 2; })
    .map(function(k) { return result[k]; });

console.log(pairs);

score 0 · Answer 2 · answered Mar 19 '18 at 10:28

We could mutate the equation:

a * b = c * d | : b
a = c * d : b

So actually we just need to get all different combinations of three numbers (b, c, d) and check if the result (a) is also in the given range:

while(true){
  // shuffle
  const [b, c, d] = items;
  const a = c * d / b;
  if(items.includes(a + ""))
     return true;
}
return false;

Now you only need to shuffle the array to go through all different combinations. You can find an algorithm here

score 0 · Answer 3 · answered Mar 19 '18 at 10:35

Assuming that you are given an array such as [1,2,3,7,8,9,6] and a value 18 and you need to find pairs that multiply to 18 then, use the following approach

Convert them to a map - O(n)

var inputArr = [1,2,3,7,8,9,6];
var map = inputArr.reduce( (acc, c) => {
   acc[ c ] = true; //set any truthy value
   return acc;
},{});

Iterate an inputArr and see if its compliment is available in the map - O(n)

var output = [];
var mulValue = 18;
inputArr.forEach( s => {
   var remainder = mulValue/s;
   if ( map[s] && map[remainder] )
   {
      output.push( [ s, remainder ] );
      map[s] = false;
      map[remainder] = false;
   }
});

Demo

var inputArr = [1, 2, 3, 7, 8, 9, 6];
var map = inputArr.reduce((acc, c) => {
  acc[c] = true; //set any truthy value
  return acc;
}, {});

var output = [];
var mulValue = 18;
inputArr.forEach(s => {
  var remainder = mulValue / s;
  if (map[s] && map[remainder]) {
    output.push([s, remainder]);
    map[s] = false;
    map[remainder] = false;
  }
});

console.log(output);

score 0 · Answer 4 · edited Jun 20 '20 at 09:12

You can try something like this:

Idea:

Loop over the array to compute product. Use this iterator(say i) as get first operand(say op1).
Now again loop over same array but the range will start from i+1. This is to reduce number of iteration.
Now create a temp variable that will hold product and operand.
On every iteration, add value to product in hashMap.
Now loop over hashMap and remove any value that has length that is less than 2.

function sameProductValues(arr) {
  var hashMap = {};
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = i + 1; j < arr.length; j++) {
      var product = arr[i] * arr[j];
      hashMap[product] = hashMap[product] || [];
      hashMap[product].push([arr[i], arr[j]]);
    }
  }

  for(var key in hashMap) {
    if( hashMap[key].length < 2 ) {
      delete hashMap[key];
    }
  }
  
  console.log(hashMap)
}

sameProductValues([1, 2, 3, 7, 8, 9, 6])

How do I find all 2 pairs of integers that have the same product in JavaScript?

4 Answers4

Idea: