 # P2D - Editorial

Practice
Source

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={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;
}
``````