Lemonade Change
Basic Greedy Problems DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Providing correct change to customers in a queue using limited denominations, Greedy Algorithm, Arrays, Frequency Counting, Conditional Statements, space complexity, greedy algorithm, general programming, conditional logic, array traversal, Coin Change Problem, State Tracking, Loops & Iteration.
Problem Statement 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 the input array). 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. Important Notes: You do not have any change in hand at first. You must provide change to customers in the order they appear in the queue. Return true if and only if you can provide every customer with the correct change, otherwise return false. Input Specification An integer array bills where bills[i] is the bill the i th customer pays with. Output Specification Return true if you can provide correct change to every customer, otherwise return false. Constraints 0 ≤ bills.length ≤ 10^5 bills[i] will be either 5, 10, or 20. Sample Test Cases Sample Input 1 Sample Output 1 Explanation: From the first 3 customers, we collect three $5 bills. 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 return true. Sample Input 2 Sample Output 2 Explanation: From the first two customers, we collect two $5 bills. For the next two customers, 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 could get correct change, we return false. Difficulty Level Easy