Minimum number of notes

CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

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 by referring some online programming courses. ( 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)
Previous post Benchmates
Next post Saitama’s Punch

Leave a Reply

Your email address will not be published. Required fields are marked *