Coin Change Total Number of Ways in DSA Java - 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 Java 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 integer array called coins with the exact values 1, 2, 5

Create an integer variable called amount and set it to 5

Write a method 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 in different ways.

💼 Career

Understanding dynamic programming and coin change problems is useful for software engineers working on financial software, e-commerce, and algorithm design.

1

Create the coin denominations array

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

DSA Java

// Create the integer array coins with values 1, 2, 5
// Your code here

Hint

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

2

Set the amount to make change for

Create an integer variable called amount and set it to 5 inside the main method, below the coins array.

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        // Create the integer variable amount and set it to 5
        // Your code here
    }
}

Hint

Use int amount = 5; to create the variable.

3

Write the method to count ways to make change

Write a static method called countWays that takes an integer array coins and an integer amount as parameters and returns an integer. Use a dynamic programming approach with an integer array dp of size amount + 1. Initialize dp[0] to 1. For each coin in coins, update dp[j] by adding dp[j - coin] for all j from coin to amount. Return dp[amount]. Place this method inside the CoinChange class but outside the main method.

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
    }

    // Write the countWays method below
    // Your code here
}

Hint

Use two nested loops: one over coins and one from coin to amount. Update dp array accordingly.

4

Print the total number of ways to make change

Inside the main method, after declaring coins and amount, write a print statement that calls countWays(coins, amount) and prints the result.

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 5;
        // Print the result of countWays(coins, amount)
        // Your code here
    }

    public static int countWays(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }
}

Hint

Use System.out.println(countWays(coins, amount)); to print the result.

Practice

1. What does the "Coin Change Total Number of Ways" problem ask you to find?

easy

A. The total number of ways to make a given amount using unlimited coins of given denominations

B. The minimum number of coins needed to make a given amount

C. The maximum value of coins that can be used to make a given amount

D. The total number of coins available in the input array

Solution

1. Step 1: Understand the problem statement

   The problem asks for counting all possible ways to form a target amount using unlimited coins of given denominations.

2. Step 2: Differentiate from similar problems

   Unlike minimum coins problem, here we count ways, not minimize coins.

3. Final Answer:

   The total number of ways to make a given amount using unlimited coins of given denominations -> Option A

4. Quick Check:

   Count ways, not minimum coins [OK]

Hint: Count combinations, not minimum coins needed [OK]

Common Mistakes:

• Confusing with minimum coins problem
• Thinking about maximum coin value
• Counting coins instead of ways

2. Which of the following Java code snippets correctly initializes the DP array for the Coin Change Total Number of Ways problem for amount 5?

easy

A. int[] dp = new int[6]; dp[0] = 1;

B. int[] dp = new int[5]; dp[0] = 1;

C. int[] dp = new int[6]; dp[1] = 1;

D. int[] dp = new int[5]; dp[1] = 1;

Solution

1. Step 1: Determine DP array size

   For amount 5, dp array size should be 6 to include index 0 to 5.

2. Step 2: Initialize base case

   dp[0] = 1 means one way to make amount 0 (using no coins).

3. Final Answer:

   int[] dp = new int[6]; dp[0] = 1; -> Option A

4. Quick Check:

   dp size = amount+1, dp[0] = 1 [OK]

Hint: DP array size = amount + 1; dp[0] = 1 base case [OK]

Common Mistakes:

• Using dp array size equal to amount instead of amount+1
• Initializing dp[1] instead of dp[0]
• Forgetting to set base case dp[0] = 1

3. What is the output of the following Java code snippet?

int[] coins = {1, 2};
int amount = 3;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
  for (int i = coin; i <= amount; i++) {
    dp[i] += dp[i - coin];
  }
}
System.out.println(dp[amount]);

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0] initially, dp[0] = 1.

2. Step 2: Process coin 1

   For i=1 to 3: dp[1]+=dp[0]=1, dp[2]+=dp[1]=1, dp[3]+=dp[2]=1; dp = [1,1,1,1]

3. Step 3: Process coin 2

   For i=2 to 3: dp[2]+=dp[0]=1+1=2, dp[3]+=dp[1]=1+1=2; dp = [1,1,2,2]

4. Step 4: Final dp[3]

   dp[3] = 2 means 2 ways: {1+1+1, 1+2}

5. Final Answer:

   2 -> Option C

6. Quick Check:

   Ways to make 3 with coins 1,2 = 2 [OK]

Hint: Add ways for each coin from coin to amount [OK]

Common Mistakes:

• Not updating dp correctly inside nested loops
• Confusing dp[i] with dp[i-1]
• Miscounting combinations

4. Identify the error in the following Java code for Coin Change Total Number of Ways:

int[] coins = {1, 2, 3};
int amount = 4;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 1; i <= amount; i++) {
  for (int coin : coins) {
    if (i >= coin) {
      dp[i] += dp[i - coin];
    }
  }
}
System.out.println(dp[amount]);

medium

A. The dp array size is too small

B. dp[0] should be initialized to 0

C. The condition i >= coin is incorrect

D. The outer loop should iterate over coins, inner over amounts

Solution

1. Step 1: Analyze loop order

   Outer loop iterates over amounts, inner over coins, which counts permutations, not combinations.

2. Step 2: Correct loop order

   Outer loop should iterate over coins, inner over amounts to count combinations correctly.

3. Final Answer:

   The outer loop should iterate over coins, inner over amounts -> Option D

4. Quick Check:

   Loop order affects counting ways [OK]

Hint: Outer loop coins, inner loop amounts for combinations [OK]

Common Mistakes:

• Swapping loop order causing wrong counts
• Incorrect dp initialization
• Misusing conditions inside loops

5. Given coins = {1, 3, 5} and amount = 7, how many total ways are there to make amount 7 using unlimited coins? Use the Coin Change Total Number of Ways approach.

hard

A. 5

B. 4

C. 6

D. 7

Solution

1. Step 1: Initialize dp array

   dp size = 8, dp[0] = 1, others 0.

2. Step 2: Process coin 1

   Update dp for i=1 to 7: dp[i] += dp[i-1], dp = [1,1,1,1,1,1,1,1]

3. Step 3: Process coin 3

   For i=3 to 7: dp[3]+=dp[0]=2, dp[4]+=dp[1]=2, dp[5]+=dp[2]=2, dp[6]+=dp[3]=3, dp[7]+=dp[4]=3; dp = [1,1,1,2,2,2,3,3]

4. Step 4: Process coin 5

   For i=5 to 7: dp[5]+=dp[0]=3, dp[6]+=dp[1]=4, dp[7]+=dp[2]=4; dp = [1,1,1,2,2,3,4,4]

5. Final Answer:

   4 -> Option B

6. Quick Check:

   Count ways with coins 1,3,5 for amount 7 = 4 [OK]

Hint: Add ways coin by coin updating dp array [OK]

Common Mistakes:

• Miscounting dp updates for each coin
• Forgetting base case dp[0] = 1
• Mixing permutations with combinations