Problem Statement:
You are selling a Juice for RS 5.
Initially you will not have any change left with you.
Customers can buy the juice with either “5”, “10” or “20” RS.
You need to provide them with exact change, and you need to return true if you are able to provide them with exact change.
Example
Input: [5,5,10]
Output: true
First 2 customers pay you with two 5 rs.
3rd customer will give you 10 RS and you will return him 5 Rs.
Solution
This is a greedy problem because we choose to return the maximum denomination while giving change to customer.
We need to return the maximum denomination because we need to use smaller change for future.
SO because of that you can skip counting 20 denomination, because you will never give 20 rs to any customer.
So based on that we can write the below statements:
if (customer pays with $5) five++;
if (customer pays with $10) ten++, five–;
if (customer pays with $20) ten–, five– or five -= 3;
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
int juice_change(vector<int> amount)
{
int five = 0, ten = 0;
for (int i : amount)
{
if (i == 5) five++;
else if (i == 10) five--, ten++;
else if (ten > 0) ten--, five--;
else five -= 3;
if (five < 0) return false;
}
return true;
}
int main()
{
vector<int> amount = {5, 5, 10};
if(juice_change(amount))
{
cout<<"Change can be given to all customers"<<endl;
} else {
cout<<"Change cannot be given to all customers"<<endl;
}
return 0;
}
Output:
Change can be given to all customers