Make Exact Change Using the Fewest Notes

Easy15–20 min

Topics

GreedyMathDynamic Programming

Companies

AmazonPaytmPhonePe

A cash register holds unlimited notes of several denominations. The denominations are in increasing order, the smallest is 1, and every denomination is a whole multiple of the one before it (for example 1, 4, 12, 60). Given an amount, find the fewest notes that add up to exactly that amount.

A dynamic-programming table that works out the answer for every amount up to the target is correct for any denominations, but the special multiple-of-the-previous structure allows a much simpler greedy method: repeatedly take as many of the largest note as fit.

Test Case 1:

Input:notes = [1, 4, 12, 60], amount = 175

Output:10

Explanation:Take two 60s (120), four 12s (48), one 4 and three 1s: 2 + 4 + 1 + 3 = 10 notes.

Test Case 2:

Input:notes = [1, 3, 9, 27], amount = 26

Output:6

Explanation:27 is too big. Take two 9s (18), two 3s (6) and two 1s: 6 notes.

Test Case 3:

Input:notes = [1, 5, 10, 50, 100], amount = 0

Output:0

Explanation:Nothing to pay, so no notes are needed.

Constraints

◆1 ≤ notes.length ≤ 6; notes is strictly increasing, notes[0] = 1, and every note is a whole multiple of the previous one (for example 1, 4, 12, 60)
◆1 ≤ notes[i] ≤ 500
◆0 ≤ amount ≤ 3000
◆Any number of each note is available; return the fewest notes that add up to exactly amount (0 if amount is 0)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Dynamic Programming Over Every Amount

Brute

Build a table where fewest[t] is the fewest notes that make exactly t. For each total from 1 up to the target, try every note that is not larger than the total: using that note leaves total − note to be made, which the table already knows, so fewest[t] is the minimum over notes of fewest[t − note] + 1. This never assumes anything about the notes, so it is correct for any set that includes a 1 — but it fills in an entry for every amount up to the target, even though only a handful of them matter.

TimeO(amount × notes)

SpaceO(amount)

Java

Try it out

class Solution {
    public int fewestNotes(int[] notes, int amount) {
        int[] fewest = new int[amount + 1];
        for (int total = 1; total <= amount; total++) {
            fewest[total] = Integer.MAX_VALUE;
            for (int note : notes) {
                if (note <= total && fewest[total - note] + 1 < fewest[total]) {
                    fewest[total] = fewest[total - note] + 1;
                }
            }
        }
        return fewest[amount];
    }
}

Optimal — Take as Many of the Largest Note as Fit, Then Move Down

Optimal

Because every note is a whole multiple of the one below it, the largest note never gets in the way: any set of smaller notes that adds up to at least the largest note can be swapped for one largest note without using more notes. So taking as many of the largest note as fit is always safe. Do that, keep the remainder, and repeat with the next note down. Each note needs one division and one remainder, so the work depends only on how many kinds of notes exist — not on the amount.

TimeO(notes)

SpaceO(1)