Least denomination

At a cash counter in More retail store in India, for the cashier, system should recommend the change to be returned with least number of coins.
Following are the denominations available in rupees and paise.

25 paise, 50 paise, 5 paise, 10 paise, 20 paise, 1 paise, 2 paise, 1 rupee,  2 rupees and 5 rupees.

Based on the user input of value entered, system should come up with the least number of coins.

How to solve this problem??


Search for Coin Changing Problem on Internet.

This problem can be better solved using Dynamic Programming.

For explanation you may check this link:

For Implementation You can visit this link: