Greedy coin change

Write codeEasy14 min

Your task

A parking kiosk hands change back out of the hopper it has on hand. coin_cents[i] is what one coin of kind i is worth in cents, always at least one cent, and hopper_counts[i] is how many of that kind the hopper holds. The values are distinct and they arrive in no particular order. The kiosk pays greedily: it repeatedly takes the largest coin it still holds that is worth no more than the amount still owed, hands it over, and carries on until nothing is owed. It never takes a coin back, so it can stall on an amount that some other mix of coins would have covered. amount_cents is never negative. Return how many of each kind it paid, in the order coin_cents gives them. Return an empty list when the kiosk stalls with money still owed. Owing nothing is not a stall, so it pays a zero of every kind.

Examples

kiosk_change_payout(coin_cents: list[int], hopper_counts: list[int], amount_cents: int) -> list[int]
Example 1
Inputkiosk_change_payout([25, 10, 5], [2, 1, 3], 40)
Output[1, 1, 1]
Example 2
Inputkiosk_change_payout([25, 10], [1, 3], 30)
Output[]
Example 3
Inputkiosk_change_payout([25, 10, 5], [4, 4, 4], 0)
Output[0, 0, 0]