Header Ads Widget

Smallest Numbers of Notes | Codechef solution

     Problem:-

Consider a currency system in which there are notes of six denominations, namely, Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100.
If the sum of Rs. N is input, write a program to computer smallest number of notes that will combine to give Rs. N.

Input

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N.

Output

For each test case, display the smallest number of notes that will combine to give N, in a new line.

Constraints

  •  T  1000
  •  N  1000000

Example

Input
3 
1200
500
242

Output
12
5
7

Code:-

#include <iostream>
using namespace std;

int main() {
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int r=0,r1,a;
if(n>=100)
{
r=r+n/100;
a=r*100;
n=n-a;
}
if(n>=50)
{
r1=n/50;
r=r+r1;
a=r1*50;
n=n-a;
}
if(n>=10)
{
r1=n/10;
r=r+r1;
a=r1*10;
n=n-a;
}
if(n>=5)
{
r1=n/5;
r=r+r1;
a=r1*5;
n=n-a;
}
if(n>=2)
{
r1=n/2;
r=r+r1;
a=r1*2;
n=n-a;
}
if(n>=1)
{
r1=n/1;
r=r+r1;
a=r1*1;
n=n-a;
}
cout<<r<<endl;
}

    return 0;
}

Recommended Post:

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

Key points:-

 MCQs:-