CODEWITHSUNDEEP
javascriptalgorithmdata-structurescoin-change
Abhishek Anand
Abhishek Anand

Reputation: 477

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
}

Upvotes: 1

Views: 132

Answers (2)

MBo
MBo

Reputation: 80287

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

Upvotes: 0

Andrew Parks
Andrew Parks

Reputation: 8107

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.

Upvotes: 0

Related Questions