Practice › Greedy
Lemonade Change
Easy · Greedy · Asked at Amazon, Google, TCS, Infosys
Each lemonade costs ₹5. Customers pay with ₹5, ₹10 or ₹20 notes, in order. You start with no change. Print YES if you can give every customer correct change, otherwise NO.
Input
First line: n. Second line: n notes (each 5, 10 or 20).
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
For ₹20, prefer giving 10 + 5 over 5 + 5 + 5.
Example 1
Input
5 5 5 5 10 20
Output
YES
Example 2
Input
5 5 5 10 10 20
Output
NO
Hints
- Only ₹5 and ₹10 notes are useful as change — count how many of each you hold.
- For ₹10 give back a ₹5. For ₹20 prefer ₹10 + ₹5 (keeps more ₹5 notes, which are more flexible), else ₹5 + ₹5 + ₹5.
Approach
Track fives and tens. A ₹5 needs no change. A ₹10 needs one ₹5. A ₹20 needs ₹15: use a ₹10 and a ₹5 when you can, otherwise three ₹5s. Spending the ₹10 first is the greedy choice: ₹5 notes can make change for both ₹10 and ₹20, while ₹10 notes only help with ₹20. If change can't be made, answer NO.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int fives = 0, tens = 0;
bool ok = true;
for (int i = 0; i < n; i++) {
int note;
cin >> note;
if (note == 5) fives++;
else if (note == 10) {
if (fives == 0) ok = false;
else { fives--; tens++; }
} else {
if (tens > 0 && fives > 0) { tens--; fives--; }
else if (fives >= 3) fives -= 3;
else ok = false;
}
}
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
fives = tens = 0
ok = True
for note in data[1 : data[0] + 1]:
if note == 5:
fives += 1
elif note == 10:
if fives == 0:
ok = False
break
fives, tens = fives - 1, tens + 1
elif tens and fives:
tens, fives = tens - 1, fives - 1
elif fives >= 3:
fives -= 3
else:
ok = False
break
print("YES" if ok else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), fives = 0, tens = 0;
boolean ok = true;
for (int i = 0; i < n; i++) {
int note = sc.nextInt();
if (note == 5) fives++;
else if (note == 10) {
if (fives == 0) ok = false;
else { fives--; tens++; }
} else {
if (tens > 0 && fives > 0) { tens--; fives--; }
else if (fives >= 3) fives -= 3;
else ok = false;
}
}
System.out.println(ok ? "YES" : "NO");
}
}