Greedy Algorithm to find Minimum number of Coins

The problem, simply

You must pay an amount V. You have as many coins and notes as you like of the Indian values 1, 2, 5, 10, 20, 50, 100, 200, 500 and 2000.

Give back the smallest number of coins and notes that add up to exactly V, and which ones they are.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try everything. To pay V, try each coin as the first piece, then pay what is left in the best way, the same way. The smallest count wins.

1. If V is 0, you need 0 pieces.
2. Otherwise, for every coin c that is not more than V, the answer could be 1 + best(V - c).
3. Take the smallest of those.

class Solution {
    public int minCoins(int[] coins, int V) {
        int ans = best(coins, V);
        return ans == Integer.MAX_VALUE ? -1 : ans;      // -1 means it cannot be paid
    }

    private int best(int[] coins, int V) {
        if (V == 0) return 0;
        int best = Integer.MAX_VALUE;
        for (int c : coins) {
            if (c <= V) {
                int rest = best(coins, V - c);           // pay the rest the best way
                if (rest != Integer.MAX_VALUE) best = Math.min(best, 1 + rest);
            }
        }
        return best;
    }
}

How long it takes: every call can branch into n calls, up to V levels deep, so it can reach O(n^V). Extra room: the recursion depth, O(V). It works for any coins, but only for tiny amounts.

Way 2: the clever way

Real money is built so that the biggest piece is always a safe choice.

1. Go through the values from biggest to smallest.
2. For each value, hand over as many as fit: count = V / value, then V = V % value.
3. When V is 0, stop.

class Solution {
    private static final int[] VALUES = {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};

    public List<Integer> minPartition(int V) {
        List<Integer> paid = new ArrayList<>();
        for (int i = VALUES.length - 1; i >= 0 && V > 0; i--) {  // biggest first
            int count = V / VALUES[i];       // how many of this value fit
            V %= VALUES[i];                  // what is still left to pay
            for (int k = 0; k < count; k++) paid.add(VALUES[i]);
        }
        return paid;
    }
}

How long it takes: one step per value, O(n) for n values, plus one step per piece handed out if you list them. Extra room: O(1) besides the answer list.

Way 3: any coins, with a table

When the coins are not friendly, fill a table. best[x] is the fewest pieces to pay x. Every amount looks at the amounts it can come from by adding one coin.

class Solution {
    public int minCoins(int[] coins, int V) {
        int[] best = new int[V + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;
        for (int x = 1; x <= V; x++) {
            for (int c : coins) {
                if (c <= x && best[x - c] != Integer.MAX_VALUE) {
                    best[x] = Math.min(best[x], best[x - c] + 1);  // one more coin on top
                }
            }
        }
        return best[V] == Integer.MAX_VALUE ? -1 : best[V];
    }
}

How long it takes: O(n * V). Extra room: O(V). On coins [1, 5, 6, 9] and V = 11 it finds 2, where the greedy finds 3.

Watch out for

• Hand over many of the same piece at once with / and %. Subtracting one coin at a time is slow for large V.
• If there is no 1 coin, some amounts cannot be paid at all. Return -1 for those.
• The values must be walked from biggest to smallest. Sort them if they come in another order.

What interviewers ask next

• How can you tell if a coin set is safe for the greedy? Such a set is called canonical. A known test checks only amounts below the sum of the two biggest coins: if the greedy matches the table on all of them, it is safe everywhere.
• Count how many different ways make V? Use a table again, with the coin loop outside so each mix is counted once (LeetCode 518).
• Each coin can be used at most once? That is a 0/1 knapsack style table.
• What if V is huge, like 10^18? With friendly coins the greedy still takes O(n) steps because of / and %.

Remember this

Grown-up words: the piggy bank values are denominations, a set where the greedy is always right is a canonical coin system, and the table is the coin change dynamic program.