Pattern visualizer
Lemonade Change
Each lemonade costs $5. A $5 bill gives you change flexibility for any future customer, while a $10 bill can only help make change for a $20 bill. Therefore, the greedy rule is: when a customer gives $10, you must give one $5; when a customer gives $20 (requiring $15 change), always prefer giving one $10 and one $5 over three $5 bills. Preserving valuable $5 bills for future customers is strictly optimal. Animated on: bills = [5, 5, 5, 10, 20] — determine if you can provide every customer with correct change..
Greedy change-making with $5 and $10 bills
time O(n)space O(1)step 1 / 9
5
[0]5
[1]5
[2]10
[3]20
[4]line 2
Start with five=0, ten=0. Customer 0 pays with a $5 bill. No change required.
Pseudocode
1FUNCTION lemonadeChange(bills):2 five = 0, ten = 03 FOR each bill in bills:4 IF bill is 5: add one to five5 ELSE IF bill is 10: if no five available RETURN false, else five down one and ten up one6 ELSE: (bill is 20, needs $15 change)7 IF ten > 0 and five > 0: give one ten and one five8 ELSE IF five >= 3: give three fives9 ELSE: RETURN false10 RETURN true
← / → step · space play · Home restart