How would I sum for every number in each array each other

Question

Well, this is a challenge in Hackerrank called Electonic Shop and this is my code, it works to a certain test. When the inputs increment the time of compilation gets more time. So I need to sum for every number in one array with the other numbers for the second array.

function getMoneySpent(keyboards, drives, b) {
  let purchase = [];
  let result = -1;

  for(let i = 0; i < keyboards.length; i++) {
   for(let j = 0; j < drives.length; j++) {
     if((keyboards[i] + drives[j]) <= b) {
      purchase.push(keyboards[i] + drives[j]);
       result = Math.max(...purchase);
      } 
    }
   }
   return result;
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2 ,8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

I don't know how to make it more efficient.

I don't understand how the inputs relates to their outputs. May you please add an explanation for that? — evolutionxbox
– evolutionxbox, Commented Mar 21, 2021 at 0:51
I didn't understand, what your code was supposed to do, but at least you gave the name for this problem - i still had to search for it though. — ASDFGerte
– ASDFGerte, Commented Mar 21, 2021 at 0:51

CertainPerformance · Accepted Answer · 2021-03-21 01:00:51Z

One slight improvement would be to not to have a purchase array, but to instead call Math.max only on the current best result and the new result:

function getMoneySpent(keyboards, drives, b) {
  let result = -1;

  for (let i = 0; i < keyboards.length; i++) {
    for (let j = 0; j < drives.length; j++) {
      const newResult = keyboards[i] + drives[j];
      if (newResult < b) {
        result = Math.max(result, newResult);
      }
    }
  }
  return result;
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2, 8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

A more elaborate approach that would decrease the computational complexity would be to sort both arrays first, then have an index of comparison for both arrays, starting at the ends:

xxxxxxxx
       ^
yyyyyy
     ^

Choose one of the arrays and decrement the index until you reach the point where the sum is below b:

xxxxxxxx
       ^
yyyyyy
   ^

Then decrement the other index while increasing the current index whenever possible until the first index is at the end again:

xxxxxxxx
   ^
yyyyyy
     ^

and take the largest combination within the limit found while incrementing.

This approach would have O(n log n) complexity, due to the .sorts. (My getMoneySpent above is O(n ^ 2))

Collectives™ on Stack Overflow

How would I sum for every number in each array each other

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related