Exact Change at the Ticket Booth
EasyGreedyFree
Problem
A ticket booth sells rides for 5 credits each. Customers queue up and each pays with a single note of 5, 10 or 20 credits, in the order given by bills.
The booth opens with an empty cash drawer and must hand every customer their exact change from the notes it has collected so far. Return true if every customer can be served, false otherwise.
Example 1
- Input:
- bills = [5, 5, 5, 10, 20]
- Output:
- true
After three 5s, the 10 gets one 5 back; the 20 then gets a 10 and a 5 back.
Example 2
- Input:
- bills = [5, 5, 10, 10, 20]
- Output:
- false
When the 20 arrives the drawer holds only two 10s, so there is no way to return exactly 15.
Constraints
- 1 ≤ bills.length ≤ 10^5
- bills[i] is 5, 10 or 20
Hint
Show the first hint
You only ever need to know how many 5s and how many 10s are in the drawer.
Walkthrough
How to approach it
01Clarify before coding
- Do 20s ever help with change? No: change is at most 15, so 20s can be ignored once collected.
- Must customers be served in order? Yes, and the drawer starts empty.
- Is it enough to return a boolean? Yes; stop at the first customer who cannot be served.
02Brute force
For every 20, branch on both ways of making 15 (10 + 5 or 5 + 5 + 5) and explore all combinations to see whether any choice sequence serves everyone.
Cost: O(2^k) for k twenty-credit notes: hopeless at 10^5 customers.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.