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.
1var lemonadeChange = function(bills) {
2 let five = 0, ten = 0;
3 for (let bill of bills) {
4 if (bill === 5) five++;
5 else if (bill === 10) {
6 if (five === 0) return false;
7 five--; ten++;
8 } else {
9 if (ten > 0 && five > 0) {
10 ten--; five--;
11 } else if (five >= 3) {
12 five -= 3;
13 } else {
14 return false;
15 }
16 }
17 }
18 return true;
19};The JavaScript solution iterates over the bills array using a for-of loop. It adjusts the number of $5 and $10 bills available and returns false if an incorrect change scenario is encountered.
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.
1In Java, this solution manages the count of $5 and $10 bills for each bill processed. It attempts to provide a $10 bill where possible to improve change flexibility for future transactions.