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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 bool lemonadeChange(vector<int>& bills) {
7 int five = 0, ten = 0;
8 for (int bill : bills) {
9 if (bill == 5) five++;
10 else if (bill == 10) {
11 if (five == 0) return false;
12 five--; ten++;
13 } else {
14 if (ten > 0 && five > 0) {
15 ten--; five--;
16 } else if (five >= 3) {
17 five -= 3;
18 } else {
19 return false;
20 }
21 }
22 }
23 return true;
24 }
25};The C++ solution uses a similar approach with vector iteration to check each bill and determine if the proper change can be given, updating the count of $5 and $10 bills accordingly.
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.