You are selling lemonade at a stand where each glass costs exactly $5. Customers are standing in a queue to buy from you, and order one at a time. Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill.
You must provide the correct change to each customer so that the net transaction is exactly $5. You start with no money in your cash register. Return true if you can provide every customer with correct change, or false if you cannot.
Example 1
Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation: Customer 1, 2, and 3 give $5. You now have three $5 bills.
Customer 4 gives $10. You give one $5 in change. You now have two $5 bills and one $10 bill.
Customer 5 gives $20. You give one $10 and one $5 in change. You successfully served everyone.
Example 2
Input: bills = [5, 5, 10, 10, 20]
Output: false
Explanation: Customer 1 and 2 give $5. You have two $5 bills.
Customer 3 gives $10. You give one $5 in change. You have one $5 and one $10.
Customer 4 gives $10. You give your last $5 in change. You now have two $10 bills and zero $5 bills.
Customer 5 gives $20. You must give $15 in change, but you only have $10 bills. You cannot make change.
Approach
If you are a cashier and someone hands you a $20 bill, you owe them $15 in change. You have two choices: give them one $10 and one $5, or give them three $5 bills.
A smart cashier is greedy with their $5 bills. A $5 bill is incredibly versatile because it can be used to make change for a $10 transaction AND a $20 transaction. A $10 bill is nearly useless; it can only be used to make change for a $20 transaction. Therefore, you should always try to get rid of your useless $10 bills first and hoard your $5 bills for emergencies.
Algorithm
Keep two counters: one for
$5bills and one for$10bills. A$20bill does not need to be tracked because it is never useful for giving change.Traverse the bills in order because customers must be served exactly as they arrive.
If the current bill is
$5, increase the$5counter because no change is needed.If the current bill is
$10, give back one$5. This is required because the lemonade costs$5.If the current bill is
$20, first try to give one$10and one$5. This saves extra$5bills for future customers. If that is not possible, try to give three$5bills. If neither change option is possible, returnfalse.
If all customers are served successfully, return
true.
Dry Run
Lemonade Change Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* * Checks whether correct change can be given * to every customer in the given order. */ bool lemonadeChange(vector<int>& bills) { // Stores how many $5 bills are currently available. int five = 0; // Stores how many $10 bills are currently available. int ten = 0; for (int bill : bills) { // A $5 bill needs no change and becomes useful later. if (bill == 5) { five++; } // A $10 bill needs one $5 bill as change. else if (bill == 10) { // Without a $5 bill, correct change cannot be given. if (five == 0) { return false; } five--; ten++; } // A $20 bill needs $15 as change. else { /* * Prefer giving one $10 and one $5 * so more $5 bills are saved for later. */ if (ten > 0 && five > 0) { ten--; five--; } /* * If no $10 bill is available, three $5 bills * can still make the required $15 change. */ else if (five >= 3) { five -= 3; } // No valid way exists to give $15 change. else { return false; } } } return true; }};int main() { // Driver code starts vector<int> bills = {5, 5, 5, 10, 20}; Solution solution; cout << boolalpha << solution.lemonadeChange(bills) << endl; return 0;}Complexity Analysis
Time Complexity: O(n), where n is the number of customers, because each bill is processed once.
Space Complexity: O(1), because only constant space is used.
Interview follow-up Questions
In this specific problem, no customer will ever hand you a bill larger than $20. Because a lemonade costs $5, the maximum change you will ever need to give is $15. Therefore, a $20 bill is completely useless for making change. Storing it in a tracking variable would just waste memory.
Be the first to add a comment.