Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Only ₹5 and ₹10 notes are useful as change — count how many of each you hold.
  2. 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");
    }
}

Solve Lemonade Change online · All practice problems