In the world of Lemonade Island, you are the proud owner of a lemonade stand. Your customers line up to buy refreshing lemonade and pay with either $5, $10, or $20 bills. The challenge is to provide the correct change to each customer, ensuring that the net transaction is that the customer pays $5. To accomplish this, you need to determine if you have enough bills to give change to every customer.
Examples:
Input: N = 5, 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 received the correct change, the function returns true.Input: N = 5, bills[] = {5, 5, 10, 10, 20}
Output: False
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 cannot give change of $15 back because we only have two $10 bills. Since not every customer received the correct change, the function returns false.
Approach: To solve this problem, we can use a straightforward approach:
- We need to keep track of the count of $5 bills and $10 bills we have.
- Whenever a customer pays with a $5 bill, we increment the count of $5 bills.
- When a customer pays with a $10 bill, we decrement the count of $5 bills and increment the count of $10 bills.
- When a customer pays with a $20 bill, we try to give change by using a $10 bill and a $5 bill
- if we have any, or three $5 bills if we don’t have a $10 bill.
- If we are unable to give change in either case, we return false.
Below is the implementation of the Code:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
bool lemonadeChange(int N, vector<int>& bills)
{
// Count of $5 bills
int count5 = 0;
// Count of $10 bills
int count10 = 0;
for (int i = 0; i < N; i++) {
if (bills[i] == 5) {
count5++;
}
else if (bills[i] == 10) {
if (count5 < 1) {
// Unable to provide change
return false;
}
count5--;
count10++;
}
else if (bills[i] == 20) {
if (count10 >= 1 && count5 >= 1) {
count10--;
count5--;
}
else if (count5 >= 3) {
count5 -= 3;
}
else {
// Unable to provide change
return false;
}
}
}
return true;
}
// Drivers code
int main()
{
int N = 5;
vector<int> bills = { 5, 5, 5, 10, 20 };
// Function Call
bool result = lemonadeChange(N, bills);
cout << (result ? "True" : "False") << endl;
return 0;
}
// This code is contributed by Jeetu Bangari
Java
public class Main {
public static boolean lemonadeChange(int N, int[] bills)
{
// count of $5 bills
int count5 = 0;
// count of $10 bills
int count10 = 0;
for (int i = 0; i < N; i++) {
if (bills[i] == 5) {
count5++;
}
else if (bills[i] == 10) {
if (count5 < 1) {
// unable to provide change
return false;
}
count5--;
count10++;
}
else if (bills[i] == 20) {
if (count10 >= 1 && count5 >= 1) {
count10--;
count5--;
}
else if (count5 >= 3) {
count5 -= 3;
}
else {
// unable to provide change
return false;
}
}
}
return true;
}
public static void main(String[] args)
{
int N = 5;
int[] bills = { 5, 5, 5, 10, 20 };
boolean result = lemonadeChange(N, bills);
System.out.println(result);
}
}
// This code is contributed by Jeetu Bangari
Python3
def lemonadeChange(N, bills):
# count of $5 bills
count5 = 0
# count of $10 bills
count10 = 0
for bill in bills:
if bill == 5:
count5 += 1
elif bill == 10:
if count5 < 1:
# unable to provide change
return False
count5 -= 1
count10 += 1
elif bill == 20:
if count10 >= 1 and count5 >= 1:
count10 -= 1
count5 -= 1
elif count5 >= 3:
count5 -= 3
else:
# unable to provide change
return False
return True
N = 5
bills = [5, 5, 5, 10, 20]
result = lemonadeChange(N, bills)
print(result)
# This code is contributed by Jeetu Bangari
C#
using System;
public class Program {
public static bool LemonadeChange(int N, int[] bills)
{
// count of $5 bills
int count5 = 0;
// count of $10 bills
int count10 = 0;
for (int i = 0; i < N; i++) {
if (bills[i] == 5) {
count5++;
}
else if (bills[i] == 10) {
if (count5 < 1) {
// unable to
//provide change
return false;
}
count5--;
count10++;
}
else if (bills[i] == 20) {
if (count10 >= 1 && count5 >= 1) {
count10--;
count5--;
}
else if (count5 >= 3) {
count5 -= 3;
}
else {
// unable to
//provide change
return false;
}
}
}
return true;
}
public static void Main(string[] args)
{
int N = 5;
int[] bills = { 5, 5, 5, 10, 20 };
bool result = LemonadeChange(N, bills);
Console.WriteLine(result);
}
}
// This code is contributed by Jeetu Bangari
Javascript
function lemonadeChange(N, bills) {
// count of $5 bills
let count5 = 0;
// count of $10 bills
let count10 = 0;
for (let i = 0; i < N; i++) {
if (bills[i] === 5) {
count5++;
} else if (bills[i] === 10) {
if (count5 < 1) {
// unable to provide change
return false;
}
count5--;
count10++;
} else if (bills[i] === 20) {
if (count10 >= 1 && count5 >= 1) {
count10--;
count5--;
} else if (count5 >= 3) {
count5 -= 3;
} else {
// unable to provide change
return false;
}
}
}
return true;
}
const N = 5;
const bills = [5, 5, 5, 10, 20];
const result = lemonadeChange(N, bills);
console.log(result);
// This code is contributed by Jeetu Bangari
True
Time complexity: O(N), where N is the number of customers.
Auxiliary Space: O(1), because constant space is used.
