{"id":416,"date":"2020-06-10T05:42:00","date_gmt":"2020-06-10T05:42:00","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=416"},"modified":"2023-06-09T09:59:27","modified_gmt":"2023-06-09T09:59:27","slug":"minimum-number-of-notes","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/minimum-number-of-notes\/","title":{"rendered":"Minimum number of notes"},"content":{"rendered":"

\"\"<\/p>\n

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. <\/p>\n

How to find Minimum Number Of Notes ?<\/h2>\n
\n

Given various currency notes (<\/code>1,<\/code>2,<\/code>5,<\/code>10,<\/code>20,<\/code>50 ,<\/code>100,<\/code>500,<\/code>1000)<\/code> and N<\/code> rupees. Print the minimum number of currency notes required to exchange for the value of N<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

OBSERVATION:<\/h3>\n
\n

We need to find the minimum number of notes so we will pick notes with highest values possible to reach the value of N<\/code>. <\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
Input: N = 90\n\nOutput: 3\n\nExplanation: 1 note of 50 and 2 notes of 20 will give 90<\/code><\/pre>\n
Input: N = 100\n\nOutput: 1\n\nExplanation: 1 note of 100 is enough to give 100 <\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    Store all the currency note values in an array in ascending order. ( 1 , 2 , 5 , 10 , 20 , 50 , 100 , 500 , 1000 )<\/code><\/p>\n<\/li>\n
  2. \n
    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.<\/p>\n<\/li>\n
  3. \n
    If the value of N<\/code> is greater than the current array element, this implies that we can make use of this currency note.<\/p>\n<\/li>\n
  4. \n
    Simply divide N<\/code> 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<\/code> to N<\/code>% arr[current].<\/p>\n<\/li>\n
  5. \n
    Repeat the same process until the entire array is traversed.
    \nTotal gives us the minimum number of denominations required to be paid.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t