Coin Change Problem Using Greedy Algorithm in Java

Coin Change Problem

The Coin Change Problem is a classic example of using the greedy algorithm. In this problem, we aim to find the minimum number of coins required to make a given amount using specific denominations.

Problem Statement

Suppose you have coins of different denominations, such as {1¢, 5¢, 10¢, 25¢} (like US coins). Your task is to calculate the minimum number of coins needed to make a specific amount.

For example, if the amount is 41¢:

Use one 25¢ coin
Use one 10¢ coin
Use one 5¢ coin
Use one 1¢ coin

Total coins = 4

Step-by-Step Code Explanation

Let’s break the solution into simple steps.

Step 1: Define the Coins and the Amount

The first step is to define the denominations of coins and the target amount. For this example, we’ll use US coins {1¢, 5¢, 10¢, 25¢} and the amount 41.

int[] coins = {1, 5, 10, 25}; // Coin denominations
int amount = 41; // Amount to make

Step 2: Sort the Coins in Descending Order

Since a greedy algorithm always chooses the largest possible denomination first, we sort the coin array in descending order.

Arrays.sort(coins); 
reverseArray(coins); // Custom helper function to reverse the sorted array

The reverseArray function swaps elements from start to end until the array is reversed. This ensures our coins are in descending order like {25, 10, 5, 1}.

public static void reverseArray(int[] array) {
    int start = 0, end = array.length - 1;
    while (start < end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}

Step 3: Use the Greedy Algorithm

Now we iterate through the array and pick as many coins of the largest denomination as possible.

Divide the remaining amount by the current coin value to determine how many coins of that denomination we need.
Reduce the amount by the value of the coins used.
Count the coins used.

Here’s the loop:

for (int coin : coins) {
    if (amount >= coin) {
        int numCoins = amount / coin; // How many coins of this type
        coinCount += numCoins;       // Add to total count
        amount %= coin;              // Reduce the remaining amount
        
        System.out.println("Using " + numCoins + " coin(s) of " + coin + "¢");
    }
}

For example, if the amount is 41:

Start with 25¢: Use 1 coin, remaining amount = 41 - 25 = 16.
Next, use 10¢: Use 1 coin, remaining amount = 16 - 10 = 6.
Next, use 5¢: Use 1 coin, remaining amount = 6 - 5 = 1.
Finally, use 1¢: Use 1 coin, remaining amount = 0.

Step 4: Handle Edge Cases

If the remaining amount is not 0 after the loop, it means the exact amount cannot be made with the given coins. For example, if the denominations were {4, 7} and the amount was 5, we would print an error message.

if (amount == 0) {
    return coinCount;
} else {
    System.out.println("Cannot make exact amount with given coins.");
    return -1;
}

Complete Java Code

Here’s the complete Java code:

import java.util.Arrays;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        // Define coin denominations
        int[] coins = {1, 5, 10, 25}; // Example: US coins (1¢, 5¢, 10¢, 25¢)
        int amount = 41; // Amount to make
        
        // Sort the coins in descending order
        Arrays.sort(coins);
        reverseArray(coins);

        // Call the greedy algorithm
        int coinCount = getMinimumCoins(coins, amount);
        
        System.out.println("Minimum coins required: " + coinCount);
    }

    // Function to calculate the minimum number of coins
    public static int getMinimumCoins(int[] coins, int amount) {
        int coinCount = 0; // Count of coins used

        for (int coin : coins) {
            // Use as many coins as possible of the current denomination
            if (amount >= coin) {
                int numCoins = amount / coin;
                coinCount += numCoins; // Add the number of coins used
                amount %= coin;       // Update the remaining amount
                
                System.out.println("Using " + numCoins + " coin(s) of " + coin + "¢");
            }
        }

        // If amount becomes 0, we successfully found a solution
        if (amount == 0) {
            return coinCount;
        } else {
            System.out.println("Cannot make exact amount with given coins.");
            return -1;
        }
    }

    // Helper function to reverse an array
    public static void reverseArray(int[] array) {
        int start = 0, end = array.length - 1;
        while (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }
}

Output Example

For the input:

Coins: {1, 5, 10, 25}
Amount: 41

The program will output:

Using 1 coin(s) of 25¢
Using 1 coin(s) of 10¢
Using 1 coin(s) of 5¢
Using 1 coin(s) of 1¢
Minimum coins required: 4

Key Learning Points

Greedy Choice: Always pick the largest coin denomination available.
Sorting: Sorting helps in ensuring the largest coins are picked first.
Edge Cases: Handle situations where the exact amount cannot be made.

This problem is simple, relatable, and introduces the core concept of greedy algorithms. Perfect for beginners!