Editor

Change at the Ticket Booth

#51 · Greedy · Beginner · 45 XP · about 10 min

A ticket booth sells rides for 5 dollars each. Customers queue up and pay one at a time, each with a single 5, 10 or 20 dollar bill. The booth opens with an empty cash drawer and can only give change from the bills it has collected so far.

Write can_give_change(bills) that returns True if every customer, in order, can get the correct change, and False as soon as one cannot.

When a 20 comes in and the drawer could give either a 10 and a 5 or three 5s, the booth gives the 10 and the 5, keeping its 5s for later customers.

Examples

can_give_change([5, 5, 5, 10, 20])   # returns True
can_give_change([5, 5, 10, 10, 20])  # returns False
can_give_change([10, 5])             # returns False

In the second example each 10 takes a 5 as change, so when the 20 arrives the drawer holds two 10s and no 5s: there is no way to make 15.

Constraints

  • 0 <= len(bills) <= 10000
  • Every bill is 5, 10 or 20

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.