Making Change at the Kiosk

Easy

You sell coffee at a kiosk, and every cup costs 5. Customers come up one at a time in the order given by payments; each buys exactly one cup and pays with a 5, 10 or 20 bill. Every customer must get exact change on the spot. The cash drawer starts the day empty, so you can only give change from what earlier customers have paid. Return True if you can serve the whole line, and False if someone cannot be given change.

Example 1

payments=[5, 10, 5, 20] → True

After the first two buyers the 5 was handed back as change for the 10, then another 5 comes in. The 20 needs 15 back, and the drawer holds a 10 and a 5, which is enough.

Example 2

payments=[10, 5] → False

The very first buyer pays with a 10 while the drawer is empty, so there is no 5 to give back.

Example 3

payments=[5, 5, 5, 20, 10] → False

The 20 takes all three 5s as change, emptying the drawer, so the next buyer's 10 cannot be changed.

Constraints

1 ≤ len(payments) ≤ 10⁵
Each payments[i] is 5, 10 or 20

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Cake Slices for Guests Easy Strength of the Weaker Partner Easy Planting Along a Garden Row Easy Rise and Fall Lineup Easy Triangle From Sticks Easy

Input

payments=[5, 10, 5, 20]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.