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

Coin Change Total Number of Ways

📖 Scenario: You have a collection of coins of different values. You want to find out how many different ways you can make a certain amount of money using these coins. This is like figuring out how many different combinations of coins can add up to the total amount.

🎯 Goal: Build a program that calculates the total number of ways to make a target amount using given coin values.

📋 What You'll Learn

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

Create an integer variable called amount and set it to 5

Create an integer array called ways to store the number of ways to make each amount from 0 to amount

Use a loop to update the ways array based on each coin

Print the total number of ways to make the amount

💡 Why This Matters

🌍 Real World

This problem is useful in finance and vending machines where you need to know how many ways to give change.

💼 Career

Understanding this algorithm helps in roles involving dynamic programming, problem solving, and optimization.

1

Create the coins array and amount variable

Create an integer array called coins with the values 1, 2, and 5. Also create an integer variable called amount and set it to 5.

DSA C

// Create the coins array and amount variable
// Your code here

Hint

Use int coins[] = {1, 2, 5}; to create the coins array and int amount = 5; for the amount.

2

Create the ways array and initialize it

Create an integer array called ways with size amount + 1. Initialize all elements to 0 except ways[0] which should be set to 1.

DSA C

#include 

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;

    // Create and initialize the ways array
    // Your code here

    return 0;
}

Hint

Use int ways[amount + 1] = {0}; to create the array and then set ways[0] = 1;.

3

Update ways array using coins

Use a for loop with variable i from 0 to 2 to iterate over coins. Inside it, use another for loop with variable j from coins[i] to amount. Update ways[j] by adding ways[j - coins[i]].

DSA C

#include 

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int ways[6] = {0};
    ways[0] = 1;

    // Update ways array using coins
    // Your code here

    return 0;
}

Hint

Use nested loops: outer loop over coins with i, inner loop over amounts with j. Update ways[j] by adding ways[j - coins[i]].

4

Print the total number of ways

Print the value of ways[amount] using printf with the format "%d\n".

DSA C

#include 

int main() {
    int coins[] = {1, 2, 5};
    int amount = 5;
    int ways[6] = {0};
    ways[0] = 1;

    for (int i = 0; i < 3; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            ways[j] += ways[j - coins[i]];
        }
    }

    // Print the total number of ways
    // Your code here

    return 0;
}

Hint

Use printf("%d\n", ways[amount]); to print the result.