algoadvance

Suppose you are a cashier at a lemonade stand, and each lemonade costs $5. Customers queue up to buy from you, and they may pay with a $5, $10, or $20 bill. You need to provide them with the correct change using the bills you have so far. Initially, you start with no change.

Write a function lemonadeChange that takes in a list of integers representing the bills customers use to pay for their lemonade and returns True if you can provide every customer with the correct change, or False otherwise.

Example

Input: [5, 5, 5, 10, 20]
Output: True

Input: [5, 5, 10, 10, 20]
Output: False

Clarifying Questions

  1. Can bills be of any other value than $5, $10, and $20?
    • No, only $5, $10, and $20 bills will be used.
  2. Will the list of bills always be non-empty?
    • Yes, the list will always contain at least one bill.
  3. Is the order of bills in the list guaranteed to be the order of transactions?
    • Yes, the order in the list represents the chronological order of transactions.

Strategy

  1. Initialize Counters: Use counters to keep track of the number of $5 and $10 bills you have.
  2. Iterate Through the Bills:
    • When you receive a $5 bill, increment the count of $5 bills.
    • When you receive a $10 bill, you need to give back one $5 bill as change (if you have it); otherwise, return False.
    • When you receive a $20 bill, prefer giving back one $10 bill and one $5 bill (if you have both); otherwise, give back three $5 bills. If neither option is possible, return False.
  3. Return True if All Transactions Succeed: If you can process all the bills without running out of change, return True.

Code

def lemonadeChange(bills):
    five_dollar_count = 0
    ten_dollar_count = 0
    
    for bill in bills:
        if bill == 5:
            five_dollar_count += 1
        elif bill == 10:
            if five_dollar_count > 0:
                five_dollar_count -= 1
                ten_dollar_count += 1
            else:
                return False
        elif bill == 20:
            if ten_dollar_count > 0 and five_dollar_count > 0:
                ten_dollar_count -= 1
                five_dollar_count -= 1
            elif five_dollar_count >= 3:
                five_dollar_count -= 3
            else:
                return False
    return True

# Example usage
print(lemonadeChange([5, 5, 5, 10, 20]))  # Output: True
print(lemonadeChange([5, 5, 10, 10, 20]))  # Output: False

Time Complexity

This approach ensures that every transaction is considered in sequence and the appropriate change is given, if possible, thus ensuring all customers are satisfied.

Try our interview co-pilot at AlgoAdvance.com