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⁵ 

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 use Greedy algorithm to simplify the solution.

 
#include <stdio.h>

int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n;
    scanf("%d",&n);
    int arr[9]={1,2,5,10,20,50,100,500,1000};
    int note_count=0;
    for(int i=8;i>=0;i--)
    {
      if(arr[i]<=n)
      {
        note_count += n/arr[i];
        n %= arr[i];
      }
    }
    printf("%d\n",note_count);
  }
  return 0;
}

Never Stop Learning !!