Ticket Booth Change
A ticket costs 5 dollars. bills lists, in order, the single bill each customer pays with: a 5, a 10 or a 20. The booth starts with no money and can only give change from the bills it has collected so far. When a 20 arrives it hands back a 10 and a 5 if it has a 10, and three 5s otherwise (keeping as many 5s as possible is always best).
Return True if every customer can be given exact change, otherwise False. Return True for an empty list.
Example 1
bills [5,5,5,10,20]
returns true
Three 5s come in, the 10 takes one 5 back, and the 20 gets the 10 plus a 5.
Example 2
bills [5,5,10,10,20]
returns false
After two 5s and two 10s the booth holds two 10s and no 5, so the 20 cannot get 15 back.
Constraints
0 <= len(bills) <= 100bills[i]is 5, 10 or 20
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Best Job LineupMedium
- Cheapest Way to Merge PilesMedium
- Circular Delivery RouteMedium
- Cut So Each Letter Stays TogetherMedium
- Deal Into StraightsMedium
- Fewest Candies by RatingMedium
- Fewest Door VisitsMedium
- Fewest Flips to Balance BracketsMedium