Coin Change Minimum Coins in DSA Java - 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 and wants to find the minimum number of coins needed to make a specific amount.

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

📋 What You'll Learn

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

Create an integer variable called amount and set it to 37

Use a for loop and a dp array to find the minimum coins needed for the amount

Print the minimum number of coins needed for the amount

💡 Why This Matters

🌍 Real World

Cashiers and vending machines use this logic to give change efficiently.

💼 Career

Understanding dynamic programming and optimization problems is useful for software engineers working on finance, retail, or algorithmic challenges.

1

Create the coin denominations array

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

DSA Java

// Create the coins array with values 1, 5, 10, 25
// Your code here

Hint

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

2

Set the amount to make change for

Create an integer variable called amount and set it to 37 below the coins array.

DSA Java

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

Hint

Use int amount = 37; to create the variable.

3

Calculate minimum coins using dynamic programming

Create an integer array called dp of size amount + 1. Initialize dp[0] to 0 and all other elements to a large number like amount + 1. Use a for loop with variable i from 1 to amount inclusive. Inside it, use another for loop with variable j to iterate over coins. If coins[j] is less than or equal to i, update dp[i] to the minimum of its current value and dp[i - coins[j]] + 1.

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        int amount = 37;
        // Create dp array and fill it
        // Use nested for loops to fill dp with minimum coins
        // Your code here
    }
}

Hint

Use two nested loops: outer loop from 1 to amount, inner loop over coins. Update dp[i] with minimum coins.

4

Print the minimum number of coins needed

Print the value of dp[amount] using System.out.println.

DSA Java

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        int amount = 37;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        // Print the minimum coins needed for amount
        // Your code here
    }
}

Hint

Use System.out.println(dp[amount]); to print the result.

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 needed to make the amount

C. Number of ways to make the amount

D. Sum of all coin denominations

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Differentiate from similar problems

   It is not about counting ways or maximum coins, but the minimum coins required.

3. Final Answer:

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

4. Quick Check:

   Minimum coins = minimum coins needed [OK]

Hint: Focus on 'minimum coins' needed, not ways or sums [OK]

Common Mistakes:

• Confusing minimum coins with number of ways
• Thinking about maximum coins instead of minimum
• Ignoring the total amount requirement

2. Which of the following Java method signatures correctly represents a function to find minimum coins for a given amount?

public static int minCoins(int[] coins, int amount)

easy

A. public int minCoins(int coins, int[] amount)

B. public static int minCoins(int[] coins, int amount)

C. static void minCoins(int[] coins, int amount)

D. public static int minCoins(int amount, int[] coins)

Solution

1. Step 1: Check parameter types and order

   The method should accept an array of coin denominations and an integer amount, in that order.

2. Step 2: Check return type and modifiers

   It should return an int representing minimum coins and be static for utility use.

3. Final Answer:

   public static int minCoins(int[] coins, int amount) -> Option B

4. Quick Check:

   Correct signature = public static int minCoins(int[] coins, int amount) [OK]

Hint: Array first, amount second; return int minimum coins [OK]

Common Mistakes:

• Swapping parameter order
• Wrong return type (void instead of int)
• Missing static keyword if utility method

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

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        System.out.println(minCoins(coins, amount));
    }
}

medium

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Understand the DP array filling

   dp[i] stores minimum coins for amount i. Initialized with max (7 here) except dp[0]=0.

2. Step 2: Calculate dp values for amount=6

   Using coins {1,3,4}: - dp[1] = 1 (1 coin of 1) - dp[2] = 2 (1+1) - dp[3] = 1 (coin 3) - dp[4] = 1 (coin 4) - dp[5] = 2 (4+1) - dp[6] = min(dp[6-1]+1=dp[5]+1=3, dp[6-3]+1=dp[3]+1=2, dp[6-4]+1=dp[2]+1=3) = 2

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Minimum coins for 6 = 2 [OK]

Hint: Trace dp array updates for each amount [OK]

Common Mistakes:

• Not initializing dp array correctly
• Returning dp[amount] without checking if solution exists
• Confusing dp indices or coin subtraction

4. Find the error in the following Java code snippet for minimum coin change:

public static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

medium

A. Using Integer.MAX_VALUE causes overflow when adding 1

B. dp array size should be amount, not amount + 1

C. dp[0] should be Integer.MAX_VALUE, not 0

D. The for loop should start from 0, not 1

Solution

1. Step 1: Identify the problem with Integer.MAX_VALUE

   Adding 1 to Integer.MAX_VALUE causes integer overflow, leading to incorrect dp values.

2. Step 2: Explain correct initialization

   Use a large number less than Integer.MAX_VALUE (like amount+1) to avoid overflow when adding 1.

3. Final Answer:

   Using Integer.MAX_VALUE causes overflow when adding 1 -> Option A

4. Quick Check:

   Integer.MAX_VALUE + 1 overflows [OK]

Hint: Avoid Integer.MAX_VALUE for dp initialization to prevent overflow [OK]

Common Mistakes:

• Ignoring overflow when adding 1 to max value
• Wrong dp array size
• Incorrect dp[0] initialization

5. Given coin denominations {2, 5, 10} and amount 7, what is the minimum number of coins needed? If not possible, return -1.
Use the Coin Change Minimum Coins approach.

medium

A. 1

B. 3

C. 2

D. -1

Solution

1. Step 1: Check possible combinations for amount 7

   Coins: 2, 5, 10 - 2+5=7 (2 coins) - 5+2=7 (2 coins) - 10 is too big But 2+5=7 is valid, so minimum coins = 2.

2. Step 2: Verify if amount 7 can be formed

   Actually, 2+5=7 is valid, so minimum coins = 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   7 = 5 + 2 = 2 coins [OK]

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

Common Mistakes:

• Assuming no solution without checking combinations
• Ignoring order of coins
• Returning -1 prematurely