Coin Change Minimum Coins in DSA Javascript - Build from Scratch

Coin Change Minimum Coins

📖 Scenario: Imagine you have coins of different values and you want to pay an exact amount using the fewest coins possible. This is like when you want to buy a candy and want to give the smallest number of coins to the cashier.

🎯 Goal: You will write a program that finds the minimum number of coins needed to make a given amount using a list of coin values.

📋 What You'll Learn

Create an array called coins with the values 1, 3, and 4

Create a variable called amount and set it to 6

Write a function called minCoins that takes coins and amount as inputs and returns the minimum number of coins needed

Print the result of calling minCoins(coins, amount)

💡 Why This Matters

🌍 Real World

This problem helps in situations like giving change in shops or vending machines using the fewest coins possible.

💼 Career

Understanding this problem is useful for software engineers working on payment systems, cash registers, or any system that optimizes resource usage.

1

Create the coins array

Create an array called coins with the values 1, 3, and 4.

DSA Javascript

// Your code here

Hint

Use square brackets [] to create an array and separate values with commas.

2

Set the amount to pay

Create a variable called amount and set it to 6.

DSA Javascript

const coins = [1, 3, 4];
// Your code here

Hint

Use const to create a variable and assign the number 6.

3

Write the minCoins function

Write a function called minCoins that takes coins and amount as inputs and returns the minimum number of coins needed to make the amount. Use a simple loop and array to store minimum coins for each value from 0 to amount.

DSA Javascript

const coins = [1, 3, 4];
const amount = 6;

// Your code here

Hint

Create an array dp to store minimum coins for each amount. Start with 0 coins for amount 0. Use nested loops to update dp values.

4

Print the minimum coins needed

Print the result of calling minCoins(coins, amount).

DSA Javascript

const coins = [1, 3, 4];
const amount = 6;

function minCoins(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount];
}

// Your code here

Hint

Use console.log to print the result of minCoins(coins, amount).

Practice

1. What does the Coin Change Minimum Coins problem ask you to find?
Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount.

easy

A. Minimum number of coins needed to make the amount

B. Maximum number of coins that can be used

C. Total sum of all coin denominations

D. Number of different coin types available

Solution

1. Step 1: Understand the problem goal

   The problem asks for the fewest coins needed to reach a given amount using available coin denominations.

2. Step 2: Identify the correct interpretation

   Among the options, only the minimum number of coins needed matches the problem description.

3. Final Answer:

   Minimum number of coins needed to make the amount -> Option A

4. Quick Check:

   Minimum coins = problem goal [OK]

Hint: Focus on 'minimum coins' needed, not total or max coins [OK]

Common Mistakes:

• Confusing minimum with maximum coins
• Thinking about total sum of coins instead of count
• Ignoring the amount to be formed

2. Which of the following is the correct way to initialize the DP array for the Coin Change Minimum Coins problem in JavaScript?
const dp = new Array(amount + 1).fill(____);

easy

A. null

B. 0

C. -1

D. Infinity

Solution

1. Step 1: Understand DP array initialization

   We initialize dp array with Infinity to represent that initially no amount can be formed except 0.

2. Step 2: Confirm correct fill value

   Filling with Infinity helps us find minimum coins by comparing and updating values.

3. Final Answer:

   Infinity -> Option D

4. Quick Check:

   DP array filled with Infinity for min comparisons [OK]

Hint: Use Infinity to represent impossible amounts initially [OK]

Common Mistakes:

• Using 0 which implies amount can be formed with zero coins
• Using -1 which is not suitable for min comparisons
• Using null which causes errors in calculations

3. What will be the output of the following code?

const coins = [1, 2, 5];
const amount = 11;
function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
console.log(minCoins(coins, amount));

medium

A. 5

B. 4

C. 3

D. -1

Solution

1. Step 1: Trace DP array updates for amount 11

   Using coins 1, 2, 5, minimum coins for 11 are calculated as 3 (5+5+1) or 4 (5+2+2+2). The code finds 3 coins.

2. Step 2: Verify minimum coins count

   Actually, 11 = 5 + 5 + 1 uses 3 coins, which is minimum.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   11 = 5+5+1 = 3 coins [OK]

Hint: Check combinations starting with largest coin first [OK]

Common Mistakes:

• Counting coins incorrectly (e.g., 5 coins instead of 3)
• Returning -1 when solution exists
• Ignoring smaller coins in calculation

4. Find the error in the following code snippet for Coin Change Minimum Coins:

function minCoins(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 0; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

medium

A. Loop should start from i = 1, not 0

B. dp array should be filled with 0 instead of Infinity

C. Return statement should return dp[0] instead of dp[amount]

D. coin <= i condition should be coin < i

Solution

1. Step 1: Analyze loop start index

   The outer loop starts at i = 0, but dp[0] is base case and should not be updated. Starting at 1 avoids unnecessary updates.

2. Step 2: Confirm correct loop range

   Starting from i = 1 ensures dp values build correctly from base case.

3. Final Answer:

   Loop should start from i = 1, not 0 -> Option A

4. Quick Check:

   Start loop at 1 to build dp correctly [OK]

Hint: Start dp loops from 1, not 0, to avoid base case overwrite [OK]

Common Mistakes:

• Starting loop at 0 causing incorrect dp updates
• Filling dp with 0 causing wrong min calculations
• Wrong return index causing wrong output

5. Given coins = [2, 3, 7] and amount = 13, what is the minimum number of coins needed to make the amount?
Use the Coin Change Minimum Coins approach.

hard

A. -1

B. 4

C. 5

D. 3

Solution

1. Step 1: Try combinations to form 13

   Using coins 7, 3, and 2, one way is 7 + 3 + 3 = 13 with 3 coins.

2. Step 2: Check if fewer coins possible

   No combination uses fewer than 4 coins to make 13 with these denominations.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   13 can be formed with 4 coins minimum [OK]

Hint: Try largest coin first, then fill remainder with smaller coins [OK]

Common Mistakes:

• Assuming no solution (-1) without checking combinations
• Counting coins incorrectly
• Ignoring coin reuse possibilities