Problem of the day
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 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.
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.
13
10 2 1
The minimum number of coins to change is 3 {1, 2, 10}.
50
50
1 <= 'N' <= 10^5
Time Limit: 1 sec
Think of a recursive solution.
Approach:
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).
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).