Last Updated: 19 Dec, 2020
Minimum Coins
Moderate
Asked in companies
Bob went to his favourite bakery to buy some pastries. After picking up his favourite pastries his total bill was P cents. Bob lives in Berland where all the money is in the form of coins with denominations {1, 2, 5, 10, 20, 50, 100, 500, 1000}.
Bob is not very good at maths and thinks fewer coins mean less money and he will be happy if he gives minimum number of coins to the shopkeeper. Help Bob to find the minimum number of coins that sums to P cents (assume that Bob has an infinite number of coins of all denominations).
Input Format
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.
The first line of each test case contains a positive integer P, representing the total amount.
Output Format:
For each test case, print the minimum number of coins that sums to P.
The output for each test case is in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= P <= 10^9
Time Limit: 1 sec
Approaches
We will recursively find the minimum number of coins.
Algorithm:
Let’s say we have a recursive function ‘minimumCoinsHelper’ which will return the minimum number of coins that sums to amount P.
- Call the function: minimumCoinsHelper(P).
- If P is equal to zero, return 0.
- Make a variable ‘ans’ which stores the minimum number of coins for the current amount P. Initialise ‘ans’ with a maximum value (INT_MAX).
- Iterate on the denominations of coins:
- If the current denomination is less than or equal to amount P, then call the next recursive state and update the answer, i.e., ans = min( ans, 1 + minimumCoinsHelper(P-D) ) ( D denotes the current coin’s denomination ).
- Return the ‘ans’.
In the previous approach, we are recalculating the answer for an amount. We can optimise it by storing the answer for the amount which we have calculated.
For example, if P=5 :
We are recalculating the answer for P = 3, 2 and 1.
So since there are overlapping solutions, we can use Dynamic Programming.
Let’s make an array DP of size P+1, where DP[i] denotes the minimum number of coins that sums to amount ‘i’.
DP[0] = 0, because 0 coins are needed for 0 amount.
Initialise all other values with a maximum value (INT_MAX).
Now, iterate on the amount from 0 to P-1
- Let ‘i’ denote the current amount.
- Iterate on the denominations of coin
- If (i + D) is less than or equal to P, then update its value, i.e, DP[i+D] = min(DP[i+D], 1 + DP[i]).
DP[P] stores the minimum number of coins that sums to P.
We will greedily solve this problem by finding the number of coins we can take with the largest denomination and then with the next largest denomination and so on until the total amount becomes zero.
Algorithm:
- Start with the coin which has the largest denomination.
- Find the number of coins, we can take with this denomination and subtract the sum from the total amount.
- If the amount becomes zero, we don’t need any more coins.
- Else, move to the next largest denomination and repeat steps 2 to 4.
Similar problems