algorithm - Coin change - A test case is failing - Stack Overflow

admin管理员组

文章数量:1208153

The problem goes like this:

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.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Here's how I try to solve. But it fails for this test case: [195,265,404,396], amount 3239

Where am I going wrong? Appreciate any help.

var coinChange = function(coins, amount) {
    let ans = Infinity;
    var helper = function(coins, amount, index=0, coinsNeeded = 0){
        if(amount === 0){
            ans = Math.min(ans, coinsNeeded);
            return;
        }
        if(index >= coins.length) return;

        if(coins[index] > amount) return;
        if(amount % coins[index] === 0){
            ans = Math.min(ans, coinsNeeded + amount / coins[index]);
        }

        helper(coins, amount-coins[index], index, coinsNeeded+1);
        helper(coins, amount, index+1, coinsNeeded);
        
    }

    helper(coins, amount);

    return ans === Infinity ? -1 : ans;
    
};

console.log(coinChange([1,2,5], 11))

The problem goes like this:

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.

Example 1:

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Here's how I try to solve. But it fails for this test case: [195,265,404,396], amount 3239

Where am I going wrong? Appreciate any help.

var coinChange = function(coins, amount) {
    let ans = Infinity;
    var helper = function(coins, amount, index=0, coinsNeeded = 0){
        if(amount === 0){
            ans = Math.min(ans, coinsNeeded);
            return;
        }
        if(index >= coins.length) return;

        if(coins[index] > amount) return;
        if(amount % coins[index] === 0){
            ans = Math.min(ans, coinsNeeded + amount / coins[index]);
        }

        helper(coins, amount-coins[index], index, coinsNeeded+1);
        helper(coins, amount, index+1, coinsNeeded);
        
    }

    helper(coins, amount);

    return ans === Infinity ? -1 : ans;
    
};

console.log(coinChange([1,2,5], 11))

• algorithm
• recursion
• dynamic-programming
• coin-change

Share Improve this question Follow edited Jan 19 at 12:31 ABGR asked Jan 19 at 9:52 ABGRABGR 5,20544 gold badges3131 silver badges5555 bronze badges 11

• [195,265,404,396], amount 3239 should fail as in return -1. 3239/396 = 8 with 71 remainder but there's combination of coins that divide into 71 so the return is -1. See my answer – zer00ne Commented Jan 19 at 11:54
• Well, even I"m getting -1 for this case. However, the correct answer supposedly is 12 for the above case. @zer00ne – ABGR Commented Jan 19 at 12:08
• Explain how it is 12. My logic isn't gisting with the question? – zer00ne Commented Jan 19 at 12:12
• @zer00ne That's precisely my confusion as well. But as per the test case on leetcode, this should be 12. See the Pic. Also here: leetcode.com/problems/coin-change/submissions/1513521034 – ABGR Commented Jan 19 at 12:26
• 1 I see glad you got it, happy coding. – zer00ne Commented Jan 19 at 16:55

 |  Show 6 more comments

3 Answers 3

Sorted by: Reset to default 2

So the issue here was this line: if(coins[index] > amount) return;

It obviously works for most cases and the intention was to return when the amount is greater than the value at that index. However, it wouldn't work for say [20, 6] and 26 and it would return Infinity.

So the solution is to remove this check and instead apply it where we're taking the item:

if(coins[index] <= amount) helper(coins, amount-coins[index], index, coinsNeeded+1);

var coinChange = function(coins, amount) {
    let ans = Infinity;
    var helper = function(coins, amount, index=0, coinsNeeded = 0){
        if(amount === 0){
            ans = Math.min(ans, coinsNeeded);
            return;
        }
        if(index >= coins.length) return;

        if(amount % coins[index] === 0){
            ans = Math.min(ans, coinsNeeded + amount / coins[index]);
        }

        if(coins[index] <= amount) helper(coins, amount-coins[index], index, coinsNeeded+1);
        helper(coins, amount, index+1, coinsNeeded);
        
    }

    helper(coins, amount);

    return ans === Infinity ? -1 : ans;
    
};

console.log(coinChange([20, 6], 26));
console.log(coinChange([195,265,404,396], 3239))

I am not sure what are you doing wrong, but maybe this helps a bit. The easiest way (assuming there are no performance requirements) is to calculate the number of coins needed for ever amount up to the requested one. In your case, from 0 to 3239. Next step would be to iterate over the given amounts and for each calculate the minimum. For given amount you iterate over given coins and try to subtract that coin from amount and if the result is greater than -1, then you know that solution for amount subtracted by current coin value could be increased by 1 coin. But before persisting this number, you have to check if we already have a number for that amount and persist new number only if it is smaller (since we are looking for least amount of coins).

function coinChange(coins, amount) {
    // Initialize minCoinsForAmoint array with a large value (infinity)
    let minCoinsForAmoint = new Array(amount + 1).fill(Infinity);
    minCoinsForAmoint[0] = 0;  // Base case: 0 coins to make amount 0

    // Iterate over all amounts from 1 to the target amount
    for (let i = 1; i <= amount; i++) {
        // Try using each coin to update minCoinsForAmoint[i]
        for (let coin of coins) {
            if (i - coin >= 0) {
                minCoinsForAmoint[i] = Math.min(minCoinsForAmoint[i], minCoinsForAmoint[i - coin] + 1);
            }
        }
    }

    // If minCoinsForAmoint[amount] is still infinity, it means it's impossible to form that amount
    return minCoinsForAmoint[amount] === Infinity ? -1 : minCoinsForAmoint[amount];
}

const coins = [195,265,404,396];
const amount = 3239;
console.log(coinChange(coins, amount));

Edit: in case you are more interested in background and details of this mathematical coin change problem, check Wikipedia: Change-making problem

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects. We can use a straightforward inductive strategy.

1. (base) if amount is zero, the goal has been reached, return the empty sum, 0
2. (inductive) the amount is non-zero. If there are no coins or the amount is negative, return the out-of-bounds result, -1
3. (inductive) there is at least one coin and the amount is greater than zero. Compute the result of using the first coin, increment it, and compute the result of skipping this coin. Return the minimum of both results.

function change(coins, amount) {
  if (amount == 0) return 0                       // 1️⃣ 
  if (coins[0] == null || amount < 0) return -1   // 2️⃣
  return min(                                     // 3️⃣
    inc(change(coins, amount - coins[0])),
    change(coins.slice(1), amount)
  )
}

function min(a, b) {
  if (a == -1) return b
  if (b == -1) return a
  return Math.min(a, b)
}

function inc(a) {
  return a == -1 ? -1 : a + 1
}

console.log(change([20, 6], 26))               // => 2
console.log(change([195,265,404,396], 3239))   // => 12

The -1 is the hard part of the assignment because it conflicts with "minimum" output of your main function. -1 is less than all valid return values, so using Math.min directly will not work. My suggestion is to use helpers like min and inc to work with the out-of-bounds -1 values and avoid this complexity in your main function.

本文标签： algorithmCoin changeA test case is failingStack Overflow