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 public boolean lemonadeChange(int[] bills) {
3 int five = 0, ten = 0;
4 for (int bill : bills) {
5 if (bill == 5) five++;
6 else if (bill == 10) {
7 if (five == 0) return false;
8 five--; ten++;
9 } else {
10 if (ten > 0 && five > 0) {
11 ten--; five--;
12 } else if (five >= 3) {
13 five -= 3;
14 } else {
15 return false;
16 }
17 }
18 }
19 return true;
20 }
21}The Java solution iterates over the bills array using a for-each loop. It checks each bill, adjusting the count of $5 and $10 bills. It returns false if change cannot be provided.
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.
1using namespace std;
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5) five++;
else if (bill == 10) {
if (five == 0) return false;
five--; ten++;
} else {
if (ten > 0 && five > 0) {
ten--; five--;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
}
};The C++ solution iterates over the bills vector, prioritizing the use of the $10 bill when providing change for a $20. It checks the current state after each transaction to ensure feasibility.