Denomination (Greedy Algorithm)
Denomination (Greedy Algorithm) PROBLEM STATEMENT : John is now the cashier of his newly opened business. He has a lot of notes of each denomination (1,2,5,10,20,50,100,500,1000). He has to pay his customer a change of N rupee. Find him the minimum number of denominations required to pay back the change. Input format : First-line contains an integer T where T is the number of test cases. For every Test case: The next line contains N. Output format : For every test case print the minimum number of denominations required to pay back the change in a new line. Constraints : 1 <= T <= 70 1 <= N <= 10 5 Time Limit : 1 second Example Input/Output 1: Input: ( ) 5 35 24 100 90 23 Output: 3 3 1 3 3 Input/Output Explanation: Input: N = 90 Output: 3 Explanation: 1 note of 50 and 2 notes of 20 will give 90 Input/Output Explanation: Input: N = 100 Output: 1 Explanation: 1 note of 100 is enough to give 100 SOLUTION : (CPP) Hint: We can us...