The Bridge-Troll's Exact Change
# The Bridge-Troll's Exact Change
The troll beneath Millrace Bridge keeps a slate with a number chalked on it, and the crossing-fee must be counted out to that number exactly — no more, no less. Travellers hate parting with coins, so the wise ones hand over as few pieces as the sum allows.
You are given toll, a non-negative integer, and purse, a list of positive integers giving the value of every coin a traveller carries. The same value may appear several times; each entry in purse is a separate coin and may be used at most once.
Write fewestCoins(toll, purse), which returns the smallest number of coins that can be chosen from purse so their values sum to exactly toll. The order of the coins does not matter. Choosing no coins sums to 0. If no selection of coins sums to exactly toll, return -1.
examples
- case 1
toll of 11, purse of [1, 2, 5, 5, 10]2 — the 10 and the 1 - case 2
toll of 6, purse of [4, 4, 3, 3]2 — the two 3s; no single coin is 6, and 4+3 overshoots - case 3
toll of 7, purse of [2, 4, 6]-1 — every coin is even, so no selection is ever odd - case 4
toll of 0, purse of [3, 5]0 — nothing need change hands
- reward
- 320 XP
- signature
fewestCoins
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- empty purse, nothing owed
- a single coin pays exactly
- prefers the big coin
- duplicates are separate coins
- parity makes it impossible
- whole purse is needed
- purse too light
- greed would misfire
- heavy purse, odd slate
- heavy purse, three great coins