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 <stdbool.h>
2
3bool lemonadeChange(int* bills, int billsSize) {
4 int five = 0, ten = 0;
5 for (int i = 0; i < billsSize; i++) {
6 if (bills[i] == 5) five++;
7 else if (bills[i] == 10) {
8 if (five == 0) return false;
9 five--; ten++;
10 } else {
11 if (ten > 0 && five > 0) {
12 ten--; five--;
13 } else if (five >= 3) {
14 five -= 3;
15 } else {
16 return false;
17 }
18 }
19 }
20 return true;
21}The C solution initializes counters for $5 and $10 bills. It iterates over the array and adjusts these counters based on the bill received, ensuring the correct change can be given. The function returns false if change cannot be provided at any point.
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.
1#
The solution processes each bill, adjusting the count of $5 and $10 bills and preferring to give back a $10 bill when changing for a $20 bill. It returns false if it can't make the correct change.