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 <= 105
  • bills[i] is either 5, 10, or 20.

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;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
bills = [5,5,5,10,20]

Output

x
+
cmd
true

#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;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
bills = [5,5,5,10,20]

Output

x
+
cmd
true

#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] 
Copy The Code & Try With Live Editor

Input

x
+
cmd
bills = [5,5,10,10,20]

Output

x
+
cmd
false

#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;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
bills = [5,5,5,10,20]

Output

x
+
cmd
true
Advertisements

Demonstration


Previous
#859 Leetcode Buddy Strings Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#861 Leetcode Score After Flipping Matrix Solution in C, C++, Java, JavaScript, Python, C# Leetcode