# Minimum number of notes ### CONCEPTS USED:

Basic Mathematics

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given various currency notes `(`1`,`2`,`5`,`10`,`20`,`50` ,`100`,`500`,`1000`)` and `N` rupees. Print the minimum number of currency notes required to exchange for the value of `N`.

See original problem statement here

### OBSERVATION:

We need to find the minimum number of notes so we will pick notes with highest values possible to reach the value of `N`.

#### For Example :

``````Input: N = 90

Output: 3

Explanation: 1 note of 50 and 2 notes of 20 will give 90``````
``````Input: N = 100

Output: 1

Explanation: 1 note of 100 is enough to give 100 ``````

### SOLVING APPROACH:

1. Store all the currency note values in an array in ascending order. `( 1 , 2 , 5 , 10 , 20 , 50 , 100 , 500 , 1000 )`

2. Now start traversing the array from Right to Left as higher values are stored at the righter half of the array and we are required to find the minimum no. of denominations.

3. If the value of `N` is greater than the current array element, this implies that we can make use of this currency note.

4. Simply divide `N` with the value of the current array element and the result gives us the number of this specific currency note that can be given. Store this value in a variable, say Total and reduce the value of `N` to `N`% arr[current].

5. Repeat the same process until the entire array is traversed.
Total gives us the minimum number of denominations required to be paid.

### SOLUTIONS:

```#include <stdio.h>

int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int arr={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;
}

```
```#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
int arr={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];
}
}
cout<<note_count<<"\n";
}

return 0;
}

```
```import java.util.*;
import java.io.*;

public class Main {
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t!=0)
{
int n = sc.nextInt();
int arr[] = {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];
}
}
System.out.println(note_count);
t--;
}

}
}

```

Space Complexity: `O(1)`

[forminator_quiz id="440"]

This article tried to discuss the concept of Basic Mathematics. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Mathematics you can check out MYCODE | Competitive Programming.