DEV Community

loading...

Discussion on: Daily Challenge #262 - No One Likes Spare Change

Collapse
dry profile image
Hayden Mankin • Edited

I have to admit I fell for the naive solution until I read davidmmooneys comment. The problem is to find the least amount of coins, not to use as many of the largest denomination coin as possible.

My initial solution was as follows:

function GreedyCoinCounterFactory(denominations){
  denominations.sort((x, y) => y-x);
  return (amount) => {
    return denominations.reduce((acc, curr) => {
      acc += Math.floor(amount / curr);
      amount %= curr;
      return acc;
    }, 0);
  }
}

let coins1 = GreedyCoinCounterFactory([1,5,10,25]);
let coins2 = GreedyCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = GreedyCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 4

Notice how the last test outputs 4. using this approach we find 25 + 5 + 5 + 5 = 40, although this is true, 20 + 20 = 40 is a better solution as it uses 2 coins.

The following is an improved solution based on the fact that you can divide the problem into sub problems that are also valid. for example if 20 + 20 + 1 + 1 = 42 is the best solution for 42 then 20 + 20 = 40 and 1 + 1 = 2 must be the best solution for 40 and 2 respectively. I start with the fact that you need 0 coins to get an amount of 0, then calculate the best amount for each amount between 0 and the input.

function DynamicCoinCounterFactory(denominations) {
  return (amount) => {
    let counts = [];
    counts.push(0);

    for(let i = counts.length; i <= amount; i++) {
      let min = amount;
      for(let j = 0; j < denominations.length; j++) {
        if (i >= denominations[j]) {
          min = Math.min(min, counts[i-denominations[j]]+1)
        }
      }
      counts.push(min);
    }
    return counts[counts.length-1];
  }
}

let coins1 = DynamicCoinCounterFactory([1,5,10,25]);
let coins2 = DynamicCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = DynamicCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 2