Problem Summary
You run a lemonade shop where each lemonade costs 5.
Customers arrive sequentially and each pays with a bill of 5, 10, or 20.
If they pay with 5 → no change needed.
If they pay with 10 → you must give back 5.
If they pay with 20 → you must give back 15 using your current 5 and/or 10 bills.
Initially, you have no cash. You must decide if you can serve all customers in order while always giving correct change.
Input:
T test cases.
For each test case:
Integer n — number of customers.
Array customerBills of size n with values in {5, 10, 20}.
Output:
For each test case print:
true if you can give correct change to every customer.
false otherwise.
Constraints:
1≤T≤105
1≤n≤105
customerBills[i] ∈ {5, 10, 20}
Sum of all n over test cases ≤ 105.
Examples Explanation
Sample 1:
Input:
3
6
5 5 10 5 20 20
7
5 5 5 10 10 20 20
8
5 5 5 5 10 10 20 20
Output:
0
0
1
Interpretation: 0 means false, 1 means true.
Test case 1: 5 5 10 5 20 20
After first 4 customers, you can serve them.
5th customer pays 20 → you give back 10+5 (possible).
6th customer pays 20 → need 15 change but you don’t have enough (no 10 left to form 10+5, and not enough 5s for 5+5+5).
Result: false → 0.
Test case 2: 5 5 5 10 10 20 20
At some point, you’ll lack the combination of 10 and 5 needed to give 15 for a 20 bill.
Result: false → 0.
Test case 3: 5 5 5 5 10 10 20 20
As explained in the statement:
You accumulate enough 5s and 10s.
For both 20 payments you can give 10 + 5.
Result: true → 1.
Sample 2:
Input:
2
5
5 10 5 20 10
10
5 5 5 10 5 10 5 20 20 20
Output:
0
1
Test case 1: 5 10 5 20 10
At some point, you can't provide correct change (you will miss a 5 when needed).
Result: false → 0.
Test case 2: 5 5 5 10 5 10 5 20 20 20
You can always give correct change to each customer (enough 5s and 10s at each step).
Result: true → 1.
Approach
Pattern:
This is a classic greedy simulation / counting problem.
Naive Idea:
One might think of storing all bills and trying combinations when a 20 appears, but:
Searching combinations per customer would be too slow and unnecessary.
We only ever care about how many 5 and 10 bills we have; 20 bills are never used for change.
Optimal Greedy Strategy:
We track:
count5 = how many 5 bills we currently have.
count10 = how many 10 bills we currently have.
Process customers in order:
If bill is 5
No change needed.
count5++.
If bill is 10
Need to give back 5.
If count5 > 0, then count5--, count10++.
Else → cannot give change → return false.
If bill is 20
Need to give back 15. Optimal way:Prefer to use 10 + 5 if possible (uses one 10 and one 5).
If not possible, use 5 + 5 + 5 (needs three 5 bills).
If neither combination is possible → return false.
Why prefer 10 + 5 over 5 + 5 + 5?
5 bills are more versatile (needed both for returning 5 and as part of 15), so we should save them when we can.
This strategy is proven to be optimal for this problem.
If we process all customers without failing, return true.
Edge Cases:
First customer paying 10 or 20:
You start with count5 = 0 and count10 = 0, so you immediately fail → false.
Many 20s at the end:
The logic already ensures we fail as soon as we cannot give change.
The solution is O(n) per test case, but total n over all test cases is ≤ 105, so the overall runtime is fine.
Pseudo-code:
Complexity Analysis:
Let total customers over all test cases be N.
Each bill is processed once in constant time: O(N).
No sorting or extra heavy operations.
Time Complexity: O(N)
Space Complexity: O(1) We only keep a couple of integer counters.
Java code
C code
C++ code
Python code
JavaScript code
Comments
Post a Comment