Smallest Number of Notes | CodeChef Solution

Hello coders, today we are going to solve Smallest Number of Notes CodeChef Solution whose Problem Code is FLOW005.

Task

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 Format

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

Output Format

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

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 1000000

Example

Input

3 
1200
500
242

Output

12
5
7

Solution – Smallest Number of Notes | CodeChef Solution

C++

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int T;
int N;

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &N);

    // Solve
    int sum = 0;
    std::vector<int> coins = { 100, 50, 10, 5, 2, 1 };
    for (auto c : coins) {
      sum += N / c;
      N = N % c;
    }

    // Print answer
    printf("%d\n", sum);
  }
  return 0;
}

Java

import java.util.*;
class Note
{
	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		int t = s.nextInt();
		//int p=0,q=0;

		while(t>0)
		{
			
			t--; 

			int n = s.nextInt();

			int rem=n%100;
			int count=n/100;

			count=count+(rem/50);
			 rem=rem%50;
			 
			 count=count+(rem/10);
			 rem=rem%10;
			 
			 count=count+(rem/5);
			 rem=rem%5;
			 
			 count=count+(rem/2);
			 rem=rem%2;
			 
			 count=count+(rem/1);
			 rem=rem%1;
			 
			
			System.out.println(count);
	    }
}
}

Python

#Solution Provided by CodingBroz
T = int(input())
a = [100, 50, 10, 5, 2, 1]
for _ in range(T):
    n = int(input())
    b = 0
    for x in a:
        if (x <= n):
            b = b + (n // x )
            n = n % x
    print(b)        

Disclaimer: The above Problem (Smallest Number of Notes) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.