CODEWITHSUNDEEP
javascript
Erick
Erick

Reputation: 369

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

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.

Upvotes: 0

Views: 103

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370679

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))

Upvotes: 1

Related Questions