Fewest Coins

Algorithm

Medium

coins

dynamic-programming

list

Fewest Coins

The self-checkout at your retail customer dispenses change from a coin hopper, and every coin it hands out is a coin someone has to refill — the hardware team wants change made with as few coins as possible, whatever denominations happen to be loaded that day.

You are writing the dispenser's brain: given an amount and the loaded denominations, find the smallest number of coins that adds up exactly, or report that the amount cannot be made at all.

Requirements

Create a codeunit named "Change Dispenser" with one public procedure:

procedure FewestCoins(Amount: Integer; Denominations: List of [Integer]): List of [Integer]

What you may rely on — the tests never violate this:

Amount is in the smallest currency unit (cents), between 0 and 999.
Denominations contains at least one entry; every denomination is >= 1, they are all distinct, and they arrive in no particular order.

What the returned list must guarantee — all of it is graded:

Every value in the list is one of the given denominations, and the values sum to exactly Amount.
The list holds the fewest coins possible — no combination of the given denominations reaches Amount with fewer coins.
The coins are sorted in ascending order.
An Amount of 0 returns an empty list.
If no combination of the denominations sums to Amount, the procedure must raise an error with a message that contains the text impossible (lowercase).

Examples: FewestCoins(41, [1, 5, 10, 25]) = [1, 5, 10, 25]; FewestCoins(63, [1, 5, 10, 21, 25]) = [21, 21, 21] — three coins, even though 25 fits first; FewestCoins(3, [5, 10]) errors.

What the tests check

The tests call FewestCoins and verify the coin count, the exact sum, the ascending order, and that every coin is a loaded denomination. They include an amount that equals a single denomination, an amount of zero, denominations passed in shuffled order, the 63 case above where grabbing the largest coin that fits hands out too many coins, 27 from [4, 5] where the largest coin leads to a dead end that a correct answer must avoid, two impossible amounts checked via the expected error, one randomized amount against standard coins whose minimal coin count the test computes independently, and one randomized non-standard denomination set built so that grabbing the largest coin that fits is never the fewest — so neither hardcoding nor pattern-matching the examples passes.

Learn More

Hint 1

The starter's strategy — always take the largest coin that fits — hands out 25, 25, 10, 1, 1, 1 for 63 even when a 21-coin is loaded and three of those settle it. Being locally greedy is not the same as being globally fewest.

Hint 2

Greed has a second failure mode: for 27 from {4, 5} it takes five 5s and strands a remainder of 2, declaring a makeable amount impossible. The best answer may need to skip the largest coin entirely, so a single pass that never reconsiders cannot be right.

Hint 3

Work upward instead of downward: for every sub-amount from 1 to the target, the fewest coins is one more than the fewest for (sub-amount minus a denomination), taking the best over every denomination that fits and leads back to a reachable sub-amount. Remember which coin won at each sub-amount, then walk back from the target collecting them; a sub-amount no denomination can reach stays unreachable, and an unreachable target is the impossible case.

ALBusiness Central 28.4

Press Compile to check your code compiles — Submit runs the tests.

The code editor is desktop-only

Open this problem on a computer to write and run code. Reading the description, tests and discussion works fine here.