Coin Change in Java

Question

Inspired by a leetcode exercise, I wrote my own coin changer:

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

CoinType

public class CoinType implements Comparable<CoinType>{

    private final int value;

    public CoinType(int value){
        this.value = value;
    }
    public int getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "value = "+value;
    }

    @Override
    public int compareTo(CoinType o) {
        return -1 * Integer.compare(value, o.getValue()); //biggest first!
    }
}

CoinTypes

public class CoinTypes {

    private List<CoinType> coinTypes = new ArrayList<>();
    public CoinTypes(int[] samples) {
        coinTypes = new ArrayList<>(Arrays.stream(samples).mapToObj(CoinType::new).toList());
        Collections.sort(coinTypes);
    }

    public List<CoinType> getCoinTypes() {
        return coinTypes;
    }
}

Change (returned money, my bad english, sorry)

public class Change {

    private Map<CoinType, Integer> change = new HashMap<>();
    private int amount;

    public Change(int amount) {
        this.amount = amount;
    }

    public int getRemaining() {
        int sum = change.entrySet().stream().mapToInt(Change::multiply).sum();
        return amount - sum;
    }

    public static int multiply(Map.Entry<CoinType, Integer> entrySet){
        return entrySet.getKey().getValue() * entrySet.getValue();
    }

    public void add(CoinType coinType, int amount) {
        change.put(coinType, amount);
    }

    @Override
    public String toString() {
        return change.entrySet().stream().map(e -> ""+e.getValue()+" coins of "+e.getKey()).collect(Collectors.joining(","));
    }

    public int getAmountCoins() {
        return change.values().stream().mapToInt(i -> i).sum();
    }

    public boolean hasRemaining() {
        return getRemaining() != 0;
    }
}

CoinChanger

public class CoinChanger {

    private final CoinTypes coinTypes;
    public CoinChanger(int[] coinTypes) {
        this.coinTypes = new CoinTypes(coinTypes);
    }

    public Change change(int result) {
        Change change = new Change(result);
        for(CoinType coinType: coinTypes.getCoinTypes()){
            int amount = change.getRemaining() / coinType.getValue();
            change.add(coinType, amount);
        }
        if(change.hasRemaining()){
            throw new IllegalArgumentException("cannot change to that amount with my coinTypes");
        }
        return change;
    }
}

App running example

public class App{

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

        CoinChanger coinChanger = new CoinChanger(coins);
        try {
            Change change = coinChanger.change(amount);
            System.out.println(change);
        }catch (IllegalArgumentException e){
            System.out.println("cannot give change: "+e);
        }
    }
}

Answer 1

First, and most importantly, this program, as currently written, fails for some inputs where it shouldn't. For example, it can't make change for a value of 11 when using coins of values 2 and 5, even though 3*2 + 1*5 = 11

That aside, I'm not sure the CoinTypes class is doing much here. It's just a wrapper around a List<CoinType>, only ever interacted with as a way to get to that list. Using the List<CoinType> directly seems more appropriate

The CoinType class almost feels overkill as well, being a thin wrapper around an int. That said, it arguably helps a bit with readability and clarity (Map<CoinType, Integer> is more meaningful than Map<Integer, Integer>), but I'm still not a huge fan

Change::multiply does not interact with the Change object's state, and can be static. It also does not really seem like part of Change's public-facing API (no object but a Change object is expected to ever call it), so I'd argue it should be made private

Answer 2

Consider testability

It's nice to have an easy way to test a program with various inputs, in this example:

• with coins in reverse order,
• with coins that are relative primes such as [2, 5]

With the posted code, I have to change the hardcoded values in the main method, then compile and run.

The main method could use the first arg as the target amount and the remaining args as the coins to make the program testable without recompilation.

Consider input validation

The implementation will behave strangely on some inputs:

• When the target amount is negative, it may return change with negative values
• When there are duplicate coins, it may return incorrect change

Improve exception handling

Throwing IllegalArgumentException in main looks strange now, because the values used are not real arguments, but hardcoded values.

Also, it's not common to catch IllegalArgumentException, an unchecked exception, and callers of CoinChanger.change only know to do this after reading the implementation. I think a CoinChangeException checked exception would be more appropriate here.

Do not split key pieces of the algorithm

The essence of the algorithm in the posted code is:

• for each unique coin in descending order
  • remove from the remaining amount the maximum multiples of the coin

This is not easy to find in the posted code, because the important pieces are too far away from each other:

• CoinChanger finds the multiples of coins, but the ordering of coins is not visible there
• CoinChanger has CoinTypes which performs sorting, but the descending ordering is not visible
• CoinTypes has a list of CoinType, which have a comparator for reverse ordering

A related issue is that Change is used for two purposes:

• Build up the result as coin types and their counts
• Track the state of the computation: the remaining amount to change

The consequence of the above is that to piece together the algorithm, the reader has to read multiple classes, and sometimes switch back and forth between classes.

To make the algorithm easy to see, it would be best to move the descending ordering logic closer to the logic of finding multiples. For example:

• CoinChanger could sort and store the received coins in a private final int[] coinTypesInDescendingOrder.
• CoinTypes could be renamed DescendingOrderCoinTypes, and implement the sorting using a Comparator, to make that important responsibility easy to see.

And to move the responsibility of tracking the remaining amount out of Change and into CoinChanger.change. Notice that this will have the added benefit of removing from Change the unnecessary recomputing of the remaining amount.

Implementing Comparable in practice

Implementing Comparable is most useful for classes that have an obvious logical ordering. In my experience most of the time there is no single obvious logical ordering, and it makes more sense to use a Comparator with a descriptive name to perform the sorting.

When I think about ordering of coins, I naturally think of ascending order. Therefore, instead of making CoinType implement Comparable with a counter-intuitive logic, I would not implement the needed ordering in a Comparator<CoinType> with a descriptive name.

Improve naming

The naming is mostly fine, except some confusing inconsistencies in some variables:

• CoinTypes takes int[] samples... Why not name that coins?
• CoinChanger.change takes int result... Better to name that amount (as does the caller), and rename the local variable amount to count

Java issues

In CoinTypes you could avoid creating a new ArrayList and Collections.sort by using .sorted() before calling .toList().

You missed a few member variables that can be final:

• Change.change
• CoinTypes.coinTypes

Change.multiply can be private, but actually I would inline it, because it's only used in place, and it's less typing that way.

It seems getAmountCoins is never used, so it can be removed.

Keep in mind that the purpose of overriding toString is not for pretty display, but to help debugging. So I think the best implementation of Change.toString would be simply:

@Override
public String toString() {
    return change.toString();
}