Find Minimum Number Of Coins

Easy
0/40
Average time to solve is 15m
profile
Contributed by
96 upvotes
Asked in companies
AdobePaytm (One97 Communications Limited)Myntra

Problem statement

Given an infinite supply of Indian currency i.e. [1, 2, 5, 10, 20, 50, 100, 500, 1000] valued coins and an amount 'N'.


Find the minimum coins needed to make the sum equal to 'N'. You have to return the list containing the value of coins required in decreasing order.


For Example
For Amount = 70, the minimum number of coins required is 2 i.e an Rs. 50 coin and a Rs. 20 coin.
Note
It is always possible to find the minimum number of coins for the given amount. So, the answer will always exist.
Detailed explanation ( Input/output format, Notes, Images )
Input Format
The only line contains a single integer ‘N’ representing the amount.
Output Format
The only line contains the list containing the value of coins required in decreasing order.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1
13
Sample Output 1
10 2 1
Explanation of Sample Input 1
The minimum number of coins to change is 3 {1, 2, 10}.
Sample Input 2
50
Sample Output 2
50
Constraints
1 <= 'N' <= 10^5

Time Limit: 1 sec
Hint

Think of a recursive solution.

Approaches (2)
Recursion:

Approach:

 

  • Try to make all combinations.
  • The combination that sums to ‘N’ can be our answer.
  • For all such combinations, the combination that has less size is our answer as we have to use minimum number of coins.
Time Complexity

O(2^N), where ‘N’ represents the amount to be changed.

 

For each denomination, we can either include it or exclude it, leading to a binary decision tree. So the overall time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ represents the amount to be changed.

 

We have vectors ‘ans’, and ‘v’. And in the worst case, the space complexity can be O(N). So, the overall space complexity is O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Find Minimum Number Of Coins
Full screen
Console