Intermediate Exercism • java

Change

Challenge Overview

Correctly determine change to be given using the least number of coins.

Visit the change exercise on Exercism to read the full instructions and download the exercise files.

Dig Deeper

Dynamic Programming: Top Down

Dynamic Programming - Top Down

import java.util.List;
import java.util.ArrayList;

class ChangeCalculator {
    private final List<Integer> currencyCoins;

    ChangeCalculator(List<Integer> currencyCoins) {
        this.currencyCoins = currencyCoins;
    }

    List<Integer> computeMostEfficientChange(int grandTotal) {
        if (grandTotal < 0)
            throw new IllegalArgumentException("Negative totals are not allowed.");

        List<List<Integer>> coinsUsed = new ArrayList<>(grandTotal + 1);
        coinsUsed.add(new ArrayList<Integer>());

        for (int i = 1; i <= grandTotal; i++) {
            List<Integer> bestCombination = null;
            for (int coin: currencyCoins) {
                if (coin <= i && coinsUsed.get(i - coin) != null) {
                    List<Integer> currentCombination = new ArrayList<>(coinsUsed.get(i - coin));
                    currentCombination.add(0, coin);
                    if (bestCombination == null || currentCombination.size() < bestCombination.size())
                        bestCombination = currentCombination;
                }
            }
            coinsUsed.add(bestCombination);
        }

        if (coinsUsed.get(grandTotal) == null)
            throw new IllegalArgumentException("The total " + grandTotal + " cannot be represented in the given currency.");

        return coinsUsed.get(grandTotal);
    }
}

The Dynamic Programming (DP) approach is an efficient way to solve the problem of making change for a given total using a list of available coin denominations. It minimizes the number of coins needed by breaking down the problem into smaller subproblems and solving them progressively.

Explanation

Initialize Coins Usage Tracker

If the grandTotal is negative, an exception is thrown immediately.
We create a list coinsUsed, where each index i stores the most efficient combination of coins that sum up to the value i.
The list is initialized with an empty list at index 0, as no coins are needed to achieve a total of zero.

Iterative Dynamic Programming

For each value i from 1 to grandTotal, we explore all available coin denominations to find the best combination that can achieve the total i.
For each coin, we check if it can be part of the solution (i.e., if coin <= i and coinsUsed[i - coin] is a valid combination).
If so, we generate a new combination by adding the current coin to the solution for i - coin. We then compare the size of this new combination with the existing best combination and keep the one with fewer coins.

Result

After processing all values up to grandTotal, the combination at coinsUsed[grandTotal] will represent the most efficient solution.
If no valid combination exists for grandTotal, an exception is thrown.

Time and Space Complexity

The time complexity of this approach is O(n * m), where n is the grandTotal and m is the number of available coin denominations. This is because we iterate over all coin denominations for each amount up to grandTotal.

The space complexity is O(n) due to the list coinsUsed, which stores the most efficient coin combination for each total up to grandTotal.

Dynamic Programming: Bottom Up

Dynamic Programming - Bottom up

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class ChangeCalculator {

    private final List<Integer> currencyCoins;

    ChangeCalculator(List<Integer> currencyCoins) {
        this.currencyCoins = List.copyOf(currencyCoins);
    }

    List<Integer> computeMostEfficientChange(int grandTotal) {
        if (grandTotal < 0) {
            throw new IllegalArgumentException("Negative totals are not allowed.");
        }
        if (grandTotal == 0) {
            return Collections.emptyList();
        }
        Set<Integer> reachableTotals = new HashSet<>();
        ArrayDeque<List<Integer>> queue = new ArrayDeque<>(currencyCoins.stream().map(List::of).toList());

        while (!queue.isEmpty()) {
            List<Integer> next = queue.poll();
            int total = next.stream().mapToInt(Integer::intValue).sum();
            if (total == grandTotal) {
                return next;
            }
            if (total < grandTotal && reachableTotals.add(total)) {
                for (Integer coin : currencyCoins) {
                    List<Integer> toCheck = new ArrayList<>(next);
                    toCheck.add(coin);
                    queue.offer(toCheck);
                }
            }
        }

        throw new IllegalArgumentException("The total " + grandTotal + " cannot be represented in the given currency.");
    }
}

This approach starts from the coins and calculates which amounts can be made up by the coins.

The grandTotal is first validated to ensure that it is a positive number greater than 0. Two data structures are then created:

a queue to maintain a combination of coins to check
a set to keep track of the totals from the combinations that have been seen

The queue is initialized with a number of combinations that consist just each of the coins. For example, if the available coins are 5, 10 and 20, then the queue begins with three combinations:

the first combination has just 5
the second has just 10
the third has just 20

Thus, the queue contains [[5], [10], [20]].

For each combination in the queue, the loop calculates the sum of the combination. If the sum equals the desired total, it has found the combination. Otherwise new combinations are added to the queue by adding each of the coins to the end of the combination:

less than the desired total, and:
the total has not yet been “seen” (the Set’s add method returns true if a new item is being added and false if it is already in the Set)

If the total has been "seen", there is no need to recheck the amounts because shorter combinations are always checked before longer combinations.
So, if the total is encountered again, we must have found a shorter combination to reach the same amount earlier.

Continuing with the above example, the first combination contains just 5. When this is processed, the combinations [5, 5], [5, 10] and [5, 20] would be added to the end of the queue and the queue becomes [[10], [20],[5 ,5], [5, 10], [5, 20]] for the next iteration. Adding to the end of the queue ensures that the shorter combinations are checked first and allows the combination to simply be returned when the total is reached.

The total can not be reached when there are no combinations in the queue.

Recursive

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class ChangeCalculator {

    private final List<Integer> currencyCoins;

    ChangeCalculator(List<Integer> currencyCoins) {
        this.currencyCoins = List.copyOf(currencyCoins);
    }

    List<Integer> computeMostEfficientChange(int grandTotal) {
        if (grandTotal < 0) {
            throw new IllegalArgumentException("Negative totals are not allowed.");
        }
        if (grandTotal == 0) {
            return Collections.emptyList();
        }

        return currencyCoins.stream().map(coin -> {
                    int remaining = grandTotal - coin;
                    if (remaining == 0) {
                        return List.of(coin);
                    }

                    try {
                        List<Integer> result = new ArrayList<>(computeMostEfficientChange(remaining));
                        result.add(coin);
                        result.sort(Integer::compare);
                        return result;
                    } catch (IllegalArgumentException e) {
                        return Collections.<Integer>emptyList();
                    }
                })
                .filter(c -> !c.isEmpty())
                .min(Comparator.comparingInt(List::size))
                .orElseThrow(() -> new IllegalArgumentException("The total " + grandTotal + " cannot be represented in the given currency."));

    }
}

The recursive approach works by iterating through the available coins and recursively calling itself to find the most efficient change with it. It starts by validating the grandTotal argument. If valid, use a stream to go through the available coins and determines how much change is still required if the coin is included. If no more change is required, the most efficient change consists simply of the coin on its own. Otherwise it will recursively call itself to find the most efficient change for the remaining amount. The recursive call is done in a try-catch block because the method throws an IllegalArgumentionException if the change can not be made. An empty list is used to indicate when the change can not be made in the stream. The stream filters out the empty list in the next step before finding the smallest list. If the stream is empty, an IllegalArgumentException is thrown to indicate the change could not be made.

Source: Exercism java/change