Lemonade Change

Problem

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). 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 that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return `true` _if you can provide every customer with the correct change, or_ `false` _otherwise_.

Constraints

• 1 <= bills.length <= 105
• bills[i] is either 5, 10, or 20.

Solution

The problem Lemonade Change can be solved by simply keeping track of the number of $5 bills and $10 bills for each payments.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool lemonadeChange(vector<int> &bills)
    {
        int five = 0, ten = 0;
        for (int &bill : bills)
        {
            if (bill == 5)
                five += 1;
            else if (bill == 10)
            {
                ten += 1;
                if (five >= 1)
                    five -= 1;
                else
                    return false;
            }
            else if (bill == 20)
            {
                if (ten >= 1 && five >= 1)
                {
                    ten -= 1;
                    five -= 1;
                }
                else if (five >= 3)
                    five -= 3;
                else
                    return false;
            }
        }

        return true;
    }
};