Coin change - A test case is failing

Question

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

Answer 1

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.

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

Answer 3

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