I used to be pretty good at logging onto TopCoder or HackerRank and brushing up on my problem solving skills, but I have to admit its been quite some time. So when I came across the minimum number of coins problem I decided to not only solve it, but solve it many times and see the performance differences amongst the solutions.

The problem:

Given a set of n coins, each with a different value (V1 , V2, ...Vn), and a given sum S, find the minimum number of coins that add up to S.

For example, given the set of coins whose values are (1, 5, 10 ,25), the minimum coins needed to make the sum of 23 is 5.

  • 2 coins of value 10
  • 3 coins of value 1

I really enjoy this problem, not only because I can solve it, but because it's something that anyone can understand, but not everyone realizes how hard it actually is to do (efficiently).

This will be a two part post: the first showing the brute force and greedy algorithm approaches, the second showing the backtracking and dynamic programming algorithms.

Full solutions can be found at: my github

The Setup

For better or worse, I decided the solution would be repsented in one of two ways:

  1. Empty List - means no solution was possible
  2. List of Pairs, where Pair.getLeft() is the number of coins and Pair.getRight() is the value of the coin.

Brute Force

The brute force approach involves finding all the possible solutions, then finding which of all the solutions uses the least amount of coins. This is obviously going to be largely innefficient but at least it does guarantee to find the optimal solution (if it ever finishes).

I decided to recursively find all solutions with the initial empty solution of 0 coins of each. Once a result is found I find the one with the least coins or else retun an empty list if no solution was found.

public List<Pair<Integer, Integer>> solve(int sum, int... coinValues) {
    Set<List<Pair<Integer, Integer>>> allSolutions = new HashSet<>();
    List<Pair<Integer, Integer>> coinStates = Arrays.stream(coinValues).mapToObj(v -> Pair.of(0, v))
            .collect(Collectors.toList());

    solutionHelper(sum, allSolutions, coinStates);
    return allSolutions.stream().collect(Collectors.reducing(this::optimalSolution)).orElse(new ArrayList<>());
}

public void solutionHelper(int sum, Set<List<Pair<Integer, Integer>>> allSolutions,
        List<Pair<Integer, Integer>> currentSolution) {
    int currentSum = calculateSum(currentSolution);
    if (currentSum == sum) {
        allSolutions.add(currentSolution.stream().filter(p -> p.getLeft() != 0).collect(Collectors.toList()));
        return;
    }

    if (currentSum > sum) {
        return;
    }
    for (int i = 0; i < currentSolution.size(); ++i) {
        List<Pair<Integer, Integer>> updatedSolution = new ArrayList<>(currentSolution);
        Pair<Integer, Integer> updateCoin = currentSolution.get(i);
        updatedSolution.set(i, Pair.of(updateCoin.getLeft() + 1, updateCoin.getRight()));
        solutionHelper(sum, allSolutions, updatedSolution);
    }

}

The recursive call basically checks if the current solutions sum is equal to the desired sum, if it is we're done so we add it the list of all solutions. If the sum is greater than the desired sum we stop rescursing, and lastly if the sum is still less than the desired sum, I recursively call solutionHelper, once for each of the coins.

Greedy

Unlike the brute force approach, the greedy algorithm will always finish quickly. The algorithm is dead simple: always choose the largest coin value that gets me closest to the desired sum. This algorithm is the only one that requires to do some work on the passed in coin values. Choose your favorite sorting algorithm and just sort the coinValues in descending order so that largest values are first. After that the code looks like:

public List<Pair<Integer, Integer>> solve(int sum, int... coinValues) {
    int remainder = sum;
    List<Pair<Integer, Integer>> change = new ArrayList<>();
    for (int value : descendingSort(coinValues)) {
        if (remainder == 0)
            return change;
        int numCoins = remainder / value;
        remainder %= value;
        if (numCoins > 0) {
            change.add(Pair.of(numCoins, value));
        }
    }

    return (remainder == 0) ? change : new ArrayList<>();
}

So off the bat the greedy algorithm is faster and the code is much easier to follow but...

The downside: it doesn't always work.

But why???

Basically if you have a bad set of coins values (3, 5, 11, 25) and the right sum (37), the greedy algorithm always overshoots the sum and since it only goes forward and never looks back, it can never find a solution.

But thankfully, it will always find a solution with a good set of coins but may not be the optimal solution. Also you need to have an unlimited of each amount of coin.

Conclusion

Both algorithms are simple to implement but both have their downsides. One takes too long for even small scenarios, and the other isn't guaranteed to find a solution. Luckily these aren't the only algorithmic tools we can use to solve this problem.

Whats better?

The next part of this post will describe the back tracking and dynamic programming solutions which can do much better.