A ferry ticket costs 5. Customers queue up and each buys exactly one ticket, paying with a single note: a 5, a 10 or a 20. Your till starts empty, and you can only hand back notes that earlier customers paid you.
Write can_give_change(bills: list[int]) -> bool that returns True if you can give every customer the correct change, in queue order, and False if at some point you can't.
can_give_change([5, 5, 5, 10, 20]) # True
can_give_change([5, 5, 10, 10, 20]) # False the last customer needs 15 back, but the till holds 10 + 10
can_give_change([10]) # False nothing in the till yet
can_give_change([5, 5, 10, 20]) # True pay the 20 back with 10 + 5
Constraints:
1 <= len(bills) <= 10^5- every value in
billsis5,10or20
Aim for O(n) time and O(1) extra space.
Show hint
only 5s and 10s ever go back out as change. When a 20 arrives and you have more than one way to hand back 15, which way leaves you better prepared for the next customers?