Coin Change Minimum Coins in DSA C - Build from Scratch

Coin Change Minimum Coins

📖 Scenario: You are helping a cashier who needs to give change using the fewest coins possible. The cashier has coins of certain fixed values.We want to find the minimum number of coins needed to make a specific amount.

🎯 Goal: Build a program that calculates the minimum number of coins needed to make a given amount using a set of coin values.

📋 What You'll Learn

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

Create an integer variable called amount and set it to 37

Create an integer array called minCoins to store minimum coins needed for each amount from 0 to amount

Use a loop to fill minCoins with the minimum coins needed for each value up to amount

Print the minimum number of coins needed for amount

💡 Why This Matters

🌍 Real World

Cashiers and vending machines use similar logic to give change with the fewest coins.

💼 Career

Understanding dynamic programming and optimization problems is useful for software development roles involving algorithms.

1

Create the coin values array

Create an integer array called coins with these exact values: 1, 5, 10, and 25.

DSA C

#include 

int main() {
    // Create the coins array with values 1, 5, 10, 25
    // Your code here
    return 0;
}

Hint

Use int coins[] = {1, 5, 10, 25}; to create the array.

2

Set the amount to change

Create an integer variable called amount and set it to 37.

DSA C

#include 

int main() {
    int coins[] = {1, 5, 10, 25};
    // Create an integer variable amount and set it to 37
    // Your code here
    return 0;
}

Hint

Use int amount = 37; to create the variable.

3

Calculate minimum coins needed for each amount

Create an integer array called minCoins of size amount + 1. Initialize minCoins[0] to 0 and all other elements to a large number like amount + 1. Then use a for loop with variable i from 1 to amount to find the minimum coins needed for each amount. Inside this loop, use another for loop with variable j to iterate over the coins array and update minCoins[i] if using coin coins[j] reduces the number of coins needed.

DSA C

#include 

int main() {
    int coins[] = {1, 5, 10, 25};
    int amount = 37;

    // Create minCoins array of size amount + 1
    // Initialize minCoins[0] = 0 and others to amount + 1
    // Use nested loops to fill minCoins with minimum coins needed
    // Your code here

    return 0;
}

Hint

Use two nested loops: outer loop for amounts 1 to 37, inner loop for each coin. Update minCoins[i] if a smaller number of coins is found.

4

Print the minimum number of coins needed

Use printf to print the minimum number of coins needed for amount using minCoins[amount]. The output should be exactly: Minimum coins needed: 4

DSA C

#include 

int main() {
    int coins[] = {1, 5, 10, 25};
    int amount = 37;
    int minCoins[38];

    minCoins[0] = 0;
    for (int i = 1; i <= amount; i++) {
        minCoins[i] = amount + 1;
    }

    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < 4; j++) {
            if (coins[j] <= i) {
                int sub_res = minCoins[i - coins[j]];
                if (sub_res != amount + 1 && sub_res + 1 < minCoins[i]) {
                    minCoins[i] = sub_res + 1;
                }
            }
        }
    }

    // Print the minimum coins needed for amount
    // Your code here

    return 0;
}

Hint

Use printf("Minimum coins needed: %d\n", minCoins[amount]); to print the result.