Problem Statement
You are working at a lemonade stand and are given an array of integers representing the amount of money each customer pays for a lemonade. The stand only accepts $5, $10, and $20 bills. Your task is to determine if you can provide the correct change to each customer in the sequence.
Input:
- An array
billswhere each element represents the bill amount paid by a customer. The array will only contain the values 5, 10, and 20.
Output:
- Return
trueif you can provide correct change for every customer, otherwise returnfalse.
Assumptions:
- You start with no money in the register.
- You can only give change using the money you have collected from previous customers.
Examples
Example 1:
Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation:
Customer 1 pays $5: no change needed. Now we have one 5$.
Customer 2 pays $5: no change needed. Now we have two 5$.
Customer 3 pays $5: no change needed. Now we have three 5$.
Customer 4 pays $10: give one $5 bill as change. We are left with two 5$ and one 10$.
Customer 5 pays $20: give one $10 bill and one $5 bill as change. We are left with one 5$ and two 10$.
All customers receive the correct change.Example 2:
Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation:
Customer 1 pays $5: no change needed. We have now one 5$.
Customer 2 pays $5: no change needed. We have now two 5$.
Customer 3 pays $10: give one $5 bill as change. We are left with one 5$ and one 10$.
Customer 4 pays $10: give one $5 bill as change and we are left with zero 5$ and two 10$.
Customer 5 pays 20$: All we have is two 10$ and none 5$. We have to pay him 15$ and since we don't have 5$ left with us.
So, All customers did not receive the change correctly, we return false.Different Approaches:
1️⃣ Greedy Approach
Intuition:
If a customer pays with a $5 bill, it's easy because we don't need to give any change. When a customer pays with a $10 bill, we need to have a $5 bill on hand to give them the correct change.
Now, if someone pays with a $20 bill, we can give them change with one $10 bill and one $5 bill, or if we don't have a $10 bill, we need to have three $5 bills to make the change.
Approach:
- Track the Count of Bills:
- Maintain counters for $5 and $10 bills, as they are crucial for making change.
- Process Each Customer:
- For each $5 bill received, increment the $5 bill counter. Because no change is needed.
- If a customer pays with a $10 bill, provide them with $5 in change. Ensure there is at least one $5 bill to do this. If there is, give the $5 bill and keep the $10 bill. If not, it is impossible to give the correct change, and the process should stop.
- If a customer pays with a $20 bill, provide them with $15 in change. The preferred way is by giving one $10 bill and one $5 bill. If there is no $10 bill, give three $5 bills instead. If neither option is possible, providing the correct change is not feasible, and the process should stop.
- If the correct change is given to all customers, the process is successful. If at any point providing the correct change is not possible, the process fails.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
fiveCount = 0
tenCount = 0First Iteration:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 0
tenCount = 0
since bills[i] == 5$
just increment the fiveCountSecond Iteration:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 1
tenCount = 0
since bills[i] == 5$
just increment the fiveCountThird Iteration:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 2
tenCount = 0
since bills[i] == 5$
just increment the fiveCountFourth Iteration:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 3
tenCount = 0
Now, bills[i] == 10$
we have to pay back 5$ as a change.
and decrement the fiveCount.
and increment the tenCount.Fifth Iteration:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 2
tenCount = 1
Now, bills[i] == 20$
we have to pay it 15$. It could be the combination of
10$ + 5$ OR 5$ + 5$ + 5$ OR return false if we dont have that much.
Since we have one 10$ and two 5$.
Then we can pay him that 10$ and one from 5$.
and we are left with zero 10 $ and one 5$.Loop Termination:
+-----+-----+-----+-----+-----+
bills = | 5 | 5 | 5 | 10 | 20 |
+-----+-----+-----+-----+-----+
^
|
i
fiveCount = 1
tenCount = 0
Since i has exceeded the bounds of the array,
means we have served all the customers with
proper change.
return true.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find whether each customer can
be provided with correct change */
bool lemonadeChange(vector<int>& bills) {
// Counter for $5
int five = 0;
// Counter for $10
int ten = 0;
// Iterate through each customer's bill
for (int i = 0; i < bills.size(); i++) {
/* If the customer's
bill is $5 */
if (bills[i] == 5) {
// Increment $5
five++;
}
/* If the customer's
bill is $10 */
else if (bills[i] == 10) {
/* Check if there are $5
bills available to give change */
if (five) {
// Use one $5
five--;
// Receive one $10
ten++;
}
/* If no $5 bill
available, return false */
else return false;
}
/* If the customer's
bill is $20 */
else {
/* Check if there are both
$5 and $10 bills
available to give change */
if (five && ten) {
// Use one $5
five--;
// Use one $10
ten--;
}
/* If there are not enough $10 bills,
check if there are at least
three $5 bills available */
else if (five >= 3) {
// Use three $5 bills
five -= 3;
}
/* If unable to give
change, return false */
else return false;
}
}
// Return true
return true;
}
};
int main() {
vector<int> bills = {5, 5, 5, 10, 20};
cout << "Queues of customers: ";
for (int bill : bills) {
cout << bill << " ";
}
cout << endl;
Solution solution;
bool ans = solution.lemonadeChange(bills);
if (ans)
cout << "It is possible to provide change for all customers." << endl;
else
cout << "It is not possible to provide change for all customers." << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N)whereNis the number of people in the queue or the number of bills to be processed. Each customer's bill is processed exactly once. The loop iteratesNtimes, and the operations performed during each iteration are done in constant time. - Space Complexity:
O(1)because no extra space is used.