Coin Change Total Number of Ways in DSA Typescript - Build from Scratch

Coin Change Total Number of Ways

📖 Scenario: You are helping a cashier who wants to find out how many different ways they can give change for a certain amount using specific coin denominations.

🎯 Goal: Build a program that calculates the total number of ways to make change for a given amount using a list of coin denominations.

📋 What You'll Learn

Create an array called coins with the exact values 1, 2, and 5

Create a variable called amount and set it to 5

Write a function called countWays that takes coins and amount as parameters and returns the total number of ways to make change

Use a dynamic programming approach inside countWays to calculate the number of ways

Print the result of countWays(coins, amount)

💡 Why This Matters

🌍 Real World

Cashiers and vending machines use similar calculations to give change efficiently.

💼 Career

Understanding dynamic programming and counting problems is useful for software engineers working on optimization and financial applications.

1

Create the coin denominations array

Create an array called coins with the exact values 1, 2, and 5.

DSA Typescript

# Your code here

Hint

Use square brackets to create an array and separate the numbers with commas.

2

Set the amount to make change for

Create a variable called amount and set it to 5.

DSA Typescript

const coins = [1, 2, 5];
# Your code here

Hint

Use const to declare the variable and assign the value 5.

3

Write the function to count ways to make change

Write a function called countWays that takes parameters coins and amount. Use a dynamic programming approach with an array called dp to calculate the total number of ways to make change for amount using coins. Initialize dp[0] to 1. Use nested for loops: the outer loop iterates over coins with variable coin, and the inner loop iterates from coin to amount with variable j. Update dp[j] by adding dp[j - coin]. Return dp[amount] at the end.

DSA Typescript

const coins = [1, 2, 5];
const amount = 5;

# Your code here

Hint

Use an array dp to store the number of ways to make each amount. Start with dp[0] = 1 because there is one way to make amount zero (use no coins).

4

Print the total number of ways to make change

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

DSA Typescript

const coins = [1, 2, 5];
const amount = 5;

function countWays(coins: number[], amount: number): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}

# Your code here

Hint

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