Solution: Lemonade Change

Statement▼

There is a lemonade stand where customers can buy one lemonade at a time for $\$5$ and pay with a $\$5$ , $\$10$ , or $\$20$ bill. It is necessary to return the correct change to each customer so that the net transaction is completed successfully with a total payment of $\$5$ . Note that no change is available initially.

Given an integer array, bills, where bills[i] represents the bill paid by the $i^{th}$ customer, return TRUE if it is possible to provide every customer with the correct change, or FALSE otherwise.

Constraints:

$1 \leq$ bills.length $\leq 500$
bills[i] is either $5$ , $10$ , or $20$ .

The approach we will be using to solve this problem is the greedy approach. We have to make sure that for each transaction, we give a change to the customer if they provide us with a $10$ or $20$ bill. We also don’t have any change in the beginning, which means if the first transaction is other than $5$ , we cannot run the lemonade stand. We keep a greedy mindset while solving the problem e.g., when we are dealing with $20$ bills, we instantly try to return change using a $10$ and $5$ bill instead of $5$ bills.

To implement this, follow the steps below:

Create two variables, fives and tens, to maintain the number of $5$ and $10$ bills.
We iterate the bills array, and for each bill, we check the following conditions:
- If the customer pays a $5$ bill, we increment fives.
- If they pay a $10$ bill, we check if we have a $5$ bill to provide as change. If yes, we decrement fives and increment tens. Otherwise, we return FALSE.
- If the customer pays a $20$ bill, we first proceed with the greedy approach by checking if we have $10$ and $5$ bills to provide as change. If yes, we decrement tens and fives. Otherwise, we check if we have three $5$ bills. If yes, we decrement fives by $3$ . We return FALSE if we couldn’t provide the change to the customer in any way.
If the whole bills array has been processed, we know all customers have been provided with the lemonade and the correct change. Therefore, we return TRUE.

Let’s look at the illustration below for a better understanding:

Problem

Submissions

Solution: Lemonade Change

Statement▼

Constraints:

$1 \leq$ bills.length $\leq 500$
bills[i] is either $5$ , $10$ , or $20$ .

To implement this, follow the steps below:

Create two variables, fives and tens, to maintain the number of $5$ and $10$ bills.
We iterate the bills array, and for each bill, we check the following conditions:
- If the customer pays a $5$ bill, we increment fives.
- If they pay a $10$ bill, we check if we have a $5$ bill to provide as change. If yes, we decrement fives and increment tens. Otherwise, we return FALSE.
- If the customer pays a $20$ bill, we first proceed with the greedy approach by checking if we have $10$ and $5$ bills to provide as change. If yes, we decrement tens and fives. Otherwise, we check if we have three $5$ bills. If yes, we decrement fives by $3$ . We return FALSE if we couldn’t provide the change to the customer in any way.
If the whole bills array has been processed, we know all customers have been provided with the lemonade and the correct change. Therefore, we return TRUE.

Let’s look at the illustration below for a better understanding: