Question 264140 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Algorithm to get as close to zero as possible by subtracting only allowed numbers from a starting point

Let’s say we have an arbitrary integer, position that equals 1850

We also have an array of integers, components that equals [150, 200, 500]

We can reach the zero by:

  1. Subtract components[2] from position three times (500*3), making it 350
  2. Subtract components[1] from position, making it 150
  3. Subtract components[0] from position, making it 0

So, using integers from the components array, I subtracted from position until there was as little left as possible (0)

Coded example:

var components = [500, 750, 1000];
var position = 2250;

position -= components[1]; // goal is now 1500
position -= components[0] * 3; // goal is now 0

visualization

The question: is there an algorithm to determine the best way to reach zero from a number by subtracting only allowed numbers?

It would be highly preferrable that the algorithm uses the least number of components / subtractions possible.

I’ve tried a few naive methods like brute forcing, but that isn’t ideal as performance is quite important in my application.

Tags:

2

Answers


  1. 0

    You could take a backtracking and use an ordered array for having the largest values first.

    function getSum(array, sum) {
    function iter(index, temp, left) {
        if (!left) return temp;
        if (left < 0 || index >= array.length) return;
        return iter(index, [...temp, array[index]], left - array[index])
            || iter(index + 1, temp, left);
    }

    return iter(0, [], sum);
}

console.log(getSum([1000, 750, 500], 2250));
    Login or Signup to reply.
  2. 0 
    function getCombinations(array, rest) {
  function test(state, col) {
    let best = state;
    const value = array[col];

    // what's the most I can subtract with this value?
    const max = Math.floor(state.rest / value);
    // if this is the last column to check (0), subtracting 4*value, 3*, 2*, ...
    // will not yield a better result that subtracting 5*value
    // so check only the max value.
    const min = col ? 0 : max;

    for (let i = max; i >= min; --i) {
      const tmp = i ? {
        ...state,
        [value]: i,
        rest: state.rest - value * i
      } : state;
      
      const item = col ? test(tmp, col - 1) : tmp;

      // no need to check any further
      if (item.rest === 0) return item;

      if (item.rest < best.rest) best = item;
    }

    // log checked state; since this function is recursive, 
    // avoid logging the same `best` for each `col`
    col || console.log("checked", best);

    return best;
  }

  // copy and sort ASC
  array = [...array].sort((a, b) => a - b);

  const state = { rest };
  array.forEach(value => state[value] = 0); // optional

  // going from right to left (hi to lo) so that I don't have to 
  // check `col < array.length-1` all the time. 
  // this way I can check for `col !== 0` or simply `col?`
  return test(state, array.length - 1);
}

// get 3 random values
const set = new Set();
while (set.size < 3) set.add(Math.floor(Math.random() * 999 + 1));

console.log("values", ...set);

console.log(getCombinations(set, 2250));

    technically this is a brute-force algorithm trying combinations but with some short circuiting. Like avoiding some pointless combinations and returning early when a combination is found with remainder: 0.

    And it works backwards from highest to lowest value, trying to reduce the remainder as much as possible and then checking if there is a better result with a lower count for this value to ensure that when there are multiple possible results it finds the one with the lowest count first.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search