Minimum Coins

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
34 upvotes
Asked in companies
DelhiveryWalmartOla

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
60
10
24
Sample Output 1:
2
1
3
Explanation of Sample Input 1:
In the 1st test case, we need one coin of 50 cents and one coin of 10 cents.
In the 2nd test case, we need a coin of 10 cents.
In the 3rd test case, we need one coin of 20 cents and two coins of 2 cents.
Sample Input 2:
2
200
1
Sample Output 2:
2
1
Hint

Think of a recursive approach to solve the problem.

Approaches (3)
Recursive Approach

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’.
Time Complexity

O(N^P), Where N is the number of coin denominations and P is the total amount.
 

For each amount, there will be at most N recursive calls and there are a total of P number of amounts (1 to P). Thus, the final time complexity is O(N^P).

Space Complexity

O(N^P), Where N is the number of coin denominations and P is the total amount.
 

As there will be at most  N^P recursive states, so O(N^P) recursion stack space is used.

Code Solution
(100% EXP penalty)
Minimum Coins
Full screen
Console