Algorithm
Problem Name: 860. Lemonade Change
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.
Example 1:
Input: bills = [5,5,5,10,20] Output: true Explanation: From the first 3 customers, we collect three $5 bills in order. From the fourth customer, we collect a $10 bill and give back a $5. From the fifth customer, we give a $10 bill and a $5 bill. Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20] Output: false Explanation: From the first two customers in order, we collect two $5 bills. For the next two customers in order, we collect a $10 bill and give back a $5 bill. For the last customer, we can not give the change of $15 back because we only have two $10 bills. Since not every customer received the correct change, the answer is false.
Constraints:
1 <= bills.length <= 105bills[i]is either5,10, or20.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean lemonadeChange(int[] bills) {
int[] billCount = new int[3];
for (int bill : bills) {
int returnAmount = bill - 5;
for (int i = 2; i >= 0 && returnAmount > 0; i--) {
int amount = i == 2 ? 20 : (i == 1 ? 10 : 5);
if (returnAmount >= amount) {
int billsRequired = returnAmount / amount;
int billsAvailable = billCount[i];
returnAmount -= Math.min(billsRequired, billsAvailable) * amount;
billCount[i] -= Math.min(billsRequired, billsAvailable);
}
}
if (returnAmount != 0) {
return false;
}
int amountIdx = bill == 20 ? 2 : (bill == 10 ? 1 : 0);
billCount[amountIdx]++;
}
return true;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const lemonadeChange = function(bills) {
let five = 0;
let ten = 0;
for (let el of bills) {
if (el === 5) {
five += 1;
} else if (el === 10) {
if (five < 1) return false;
five -= 1;
ten += 1;
} else {
if (five > 0 && ten > 0) {
five -= 1;
ten -= 1;
} else if (five >= 3) {
five -= 3;
} else {
return false;
}
}
}
return true;
};
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def anagramMappings(self, A, B):
ind = {num: j for j, num in enumerate(B)}
return [ind[num] for num in A]
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0860_LemonadeChange
{
public bool LemonadeChange(int[] bills)
{
int fives = 0, tens = 0;
foreach (var bill in bills)
{
if (bill == 5)
fives++;
else if (bill == 10)
{
if (fives > 0)
{
fives--;
tens++;
}
else
return false;
}
else
{
if (fives > 0 && tens > 0)
{
fives--;
tens--;
}
else if (fives >= 3)
fives -= 3;
else
return false;
}
}
return true;
}
}
}
Input
Output