coin change problem javascript code

Coin Change Problem JavaScript Code

The coin change problem is a common problem in computer science where you have to determine the optimal way to make change for a certain amount of money, given a set of available coins. The problem can be solved using dynamic programming and has many different solutions. In this post, we will discuss some of the common ways to solve this problem using JavaScript.

Solution 1: Recursive Approach

The first solution is to use a recursive approach to solve the problem. This involves breaking down the problem into smaller sub-problems and recursively solving them until we reach the base case. We can then combine the results to get the final answer.

function coinChange(coins, amount) {
  if (amount === 0) {
    return 0;
  }
  
  let result = Infinity;
  
  for (let coin of coins) {
    if (amount - coin >= 0) {
      let subResult = coinChange(coins, amount - coin);
      if (subResult !== -1) {
        result = Math.min(result, subResult + 1);
      }
    }
  }
  
  return (result === Infinity ? -1 : result);
}

In the code above, we first check if the amount is zero. If it is, then we return zero because we don't need any coins to make change. We then initialize the result variable to infinity since we want to find the minimum number of coins required. We loop through each coin in our set of coins and check if the difference between the current amount and the current coin is greater than or equal to zero. If it is, then we recursively call the coinChange function with the new amount and subtract the current coin from it. We then check if the sub-result is not equal to -1, which means that we found a valid solution. We then update the result variable with the minimum value between the current result and the sub-result plus one (since we used one coin). Finally, we return the result.

Solution 2: Dynamic Programming Approach

The second solution is to use a dynamic programming approach to solve the problem. This involves creating a table to store the minimum number of coins required to make change for each amount up to the desired amount. We can then use this table to determine the answer for any given amount.

function coinChange(coins, amount) {
  let dp = new Array(amount + 1).fill(amount + 1);
  dp[0] = 0;
  
  for (let i = 1; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }
  
  return (dp[amount] > amount ? -1 : dp[amount]);
}

In the code above, we first create a new array called dp with a length of amount plus one and fill it with the value of amount plus one. We do this because we want to store the minimum number of coins required for each amount up to the desired amount, and if we set it to infinity, we won't be able to find the solution. We then set the value of dp[0] to zero since we don't need any coins to make change for zero.

We then loop through each amount from one up to the desired amount and loop through each coin in our set of coins. We check if the current coin is less than or equal to the current amount. If it is, then we update the value of dp[i] with the minimum between its current value and the value of dp[i - coins[j]] plus one (since we used one coin). Finally, we return -1 if the value of dp[amount] is greater than amount, which means that we couldn't find a solution, or we return dp[amount] since that is the minimum number of coins required to make change for the desired amount.