Last Updated: 9 Dec, 2020

Find Minimum Number Of Coins

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

We will use the greedy approach to solve our problem. The intuition behind this idea is that since we need to minimize the total number of coins needed to make the change, taking coins with large denominations (i.e. the best available option) in each iteration can yield the best overall result.

Algorithm

We will first sort the ‘denominations’ array, if not sorted.
We traverse ‘denominations’ from the end to the beginning.
- While denominations[i] is greater than or equal to ‘amount’:
  - Add denominations[i] in our answer array.
  - We subtract denominations[i] from ‘amount’.
- If ‘amount’ becomes 0, it means we have found a solution. So, we simply break from the loop.

Solve now