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.
1public class Solution {
2 public bool LemonadeChange(int[] bills) {
3 int five = 0, ten = 0;
4 foreach (int bill in 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 C# solution employs a foreach loop to handle each bill. Based on the bill type, it updates the counters and checks if the transaction is feasible, returning false if correct change cannot be given.
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.