Author: SQU_Test
DIFFICULTY:
Medium
PREREQUISITES:
Greedy, Dynamic Programming.
PROBLEM:
Huda has a LOT of money. She has n Rials in the bank. For security reasons, she wants to withdraw it in cash (we will not disclose the reasons here). The denominations for Rial(s) bills are 1, 5, 10, 20, 100. What is the minimum number of bills Huda could receive after withdrawing her entire balance?
EXPLANATION:
The problem is to minimize π₯_1 + π₯_2 + π₯_3 + π₯_4 + π₯_5 given that π₯_1 + 5 π₯_2 + 10 π₯_3 + 20 π₯_4 +100 π₯_5 = π. It is pretty simple to see that we can operate greedily: take as many 100 as we can, then 20, then 10, etc.
The solution works because each number in the sequence 1, 5, 10, 20, 100 is a divisor of the number after it.
TIME COMPLEXITY:
Time complexity of the solution is O(n).
SOLUTIONS:
Setterβs Solution
#include<iostream >
using namespace std;
int main()
{
int c[5]={100,20,10,5,1};
long t=0, n;
cin>>n;
int i =0;
while( n > 0)
{
t+= n / c[i];
n = n%c[i];
i ++;
}
cout <<t<< endl;
return 0;
}