Minimum number of notes

Last Updated on June 9, 2023 by Mayank Dham

The concept of finding the minimum number of notes refers to a problem often encountered in programming, where the goal is to determine the smallest number of currency notes required to make up a given amount.

How to find Minimum Number Of Notes ?

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[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;
}

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

int main()
{
  int t;cin>>t;
  while(t--)
  {
    int n;cin>>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];
      }
    }
    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.

Conclusion
The problem of finding the minimum number of notes required to make up a given amount is a common programming challenge. By dividing the amount by the denominations of available currency notes and utilizing an algorithm, we can determine the optimal combination of notes to form the desired amount. This problem-solving approach is crucial in scenarios such as ATM withdrawals or cash transactions, where minimizing the number of notes used is desired. By implementing an efficient algorithm, we can calculate and display the minimum number of notes needed to represent the given amount, optimizing the use of currency notes.