Question

Given an amount, write a program to find a minimum number of currency notes of different denominations that sum to the given amount. Available note denominations are 1000, 500, 100, 50, 20, 5, 1.

Answer 1

Answer:

Given an amount, find the minimum number of notes of different denominations that sum upto the given amount. Starting from the highest denomination note, try to accommodate as many notes possible for given amount.

We may assume that we have infinite supply of notes of values {2000, 500, 200, 100, 50, 20, 10, 5, 1}

Examples:

Input : 800 Output : Currency Count 500 : 1 200 : 1 100 : 1 Input : 2456 Output : Currency Count 2000 : 1 200 : 2 50 : 1 5 : 1 1 : 1