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

Debugging a leetcode solution in javascript – coin change,

I solved a leetcode question that looks correct to me, but It’s not and I am unable to understand why it is wrong. Can someone please tell me why my solution is not working
Following is the question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.

Here is my solution

var coinChange = function (coins, amount) {
coins = coins.sort((a, b) => b - a)
let cache = {}
let result = coinChangeHelper(coins, amount, 0, cache)
console.log(cache)
return result
};

var coinChangeHelper = (coins, amount, coinUsedTillNow, cache) => {
    if (cache[amount] !== undefined) {
        return cache[amount]
}

if (amount === 0) {
    return coinUsedTillNow
}

if (amount < 0) {
    return -1
}

let result = Infinity
for (let i = 0; i < coins.length; i++) {
    let temp = coinChangeHelper(coins, amount - coins[i], coinUsedTillNow + 1, cache)
    if(temp === -1)
        continue
    result = Math.min(result,temp)
}
if (result !== Infinity) {
    cache[amount] = result
    return result
}

cache[amount] = -1
return -1
}
Tags:

2

Answers


  1. 0

    Your code works perfectly when the correct course of action is always to use the highest-denomination coins first.

    For example, if the denominations are [10, 5, 2, 1], and the target amount is greater than 10, I should always use the 10 coin at least once.

    However, if the denominations are [100, 57, 50, 1], and the target amount is 107, then I should not be using the 100 coin. Your code will return 8, but the correct answer is 2.

    The problem with your code, therefore, is that it is abandoning the search without trying all possible combinations (because of the return in your for loop). You should be comparing the results of different attempts, to find the one that requires the fewest coins.

    Login or Signup to reply.
  2. 0

    You are using greedy algorithm that works for some inputs only.

    Apply dynamic programming:

    var coinChange = function (coins, amount) {
  let cache = {}
  cache[0] = 0
  for (let i = 0; i < coins.length; i++) {
      for (let j = 0; j <= amount - coins[i]; j++) {
          if (cache[j] !== undefined) {
             if (cache[j+coins[i]] === undefined) {
                cache[j+coins[i]] = cache[j] + 1
             }
             else {
                cache[j+coins[i]] = Math.min(cache[j] + 1, cache[j+coins[i]])
             }
          }
      }
    }
   return cache[amount]
}
console.log(coinChange([2,5,7],12))
console.log(coinChange([2,5,7],13))
console.log(coinChange([2,5,7],14))
console.log(coinChange([2,5,7],15))
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search