Sponsored
Sponsored
This approach involves using a greedy strategy where we maintain counters for $5 and $10 bills. When a $5 bill is received, simply increase the count. For a $10 bill, check if you have a $5 bill to give as change. For a $20 bill, prefer giving one $10 and one $5 bill as change if available, otherwise give three $5 bills.
Time Complexity: O(n), where n is the length of the bills array.
Space Complexity: O(1), since only a fixed amount of additional space is used for counters.
1class Solution:
2 def lemonadeChange(self, bills: List[int]) -> bool:
3 five, ten = 0, 0
4 for bill in bills:
5 if bill == 5:
6 five += 1
7 elif bill == 10:
8 if five == 0:
9 return False
10 five -= 1
11 ten += 1
12 else:
13 if ten > 0 and five > 0:
14 ten -= 1
15 five -= 1
16 elif five >= 3:
17 five -= 3
18 else:
19 return False
20 return TrueThe Python solution uses variables to track the count of $5 and $10 bills. It processes each bill, updating counts and checking if a transaction can be completed. The function returns false if a customer cannot receive the correct change.
This approach focuses on prioritizing the use of $10 bills when giving change to customers with $20 bills. By simulating the process, we ensure that change is handled with a clear order of preference, utilizing available higher denominations first.
Time Complexity: O(n), where n is the size of the bills array.
Space Complexity: O(1), using only fixed space for counters.
1The Python implementation manages the count of $5 and $10 bills. It prioritizes using $10 bills when giving change for a $20, which helps in maintaining sufficient change for future customer transactions.