{"id":948,"date":"2025-08-21T18:04:32","date_gmt":"2025-08-21T12:34:32","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=948"},"modified":"2025-08-21T18:04:34","modified_gmt":"2025-08-21T12:34:34","slug":"minimum-number-of-coins","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/minimum-number-of-coins\/","title":{"rendered":"Minimum number of Coins | Greedy Algorithm Solution"},"content":{"rendered":"\n

The Minimum Number of Coins<\/strong> problem is a classic Greedy Algorithm<\/strong> example. It is frequently asked in coding interviews and is a real-life inspired problem related to currency exchange and coin change systems.<\/p>\n\n\n\n

In this blog, we will carefully understand the problem statement, explore the greedy approach, and then go through the optimal Python solution with explanation and complexity analysis.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

\n\n\n\n

Problem Statement \u2013 What Does the Problem Say?<\/h2>\n\n\n\n

You are given a value N<\/strong>. Your task is to represent this value using the minimum number of coins and notes<\/strong> available in the Indian currency system.<\/p>\n\n\n\n

The available denominations are:<\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
[<\/span>2000<\/span>, <\/span>500<\/span>, <\/span>200<\/span>, <\/span>100<\/span>, <\/span>50<\/span>, <\/span>20<\/span>, <\/span>10<\/span>, <\/span>5<\/span>, <\/span>2<\/span>, <\/span>1<\/span>]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
You need to output the coins\/notes used in making the change for the given amount.<\/p>\n\n\n\n
Example 1:<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input: N = <\/span>43<\/span><\/span>\nOutput: [<\/span>20<\/span>, <\/span>20<\/span>, <\/span>2<\/span>, <\/span>1<\/span>]<\/span><\/span>\nExplanation: <\/span><\/span>\n- <\/span>20<\/span> + <\/span>20<\/span> + <\/span>2<\/span> + <\/span>1<\/span> = <\/span>43<\/span> using <\/span>4<\/span> coins\/notes.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input: N = <\/span>1000<\/span><\/span>\nOutput: [<\/span>500<\/span>, <\/span>500<\/span>]<\/span><\/span>\nExplanation:<\/span><\/span>\n- The amount <\/span>1000<\/span> can be formed using only two <\/span>500<\/span> rupee notes.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
The problem essentially asks: How can we represent the number with the least number of coins\/notes possible?<\/strong><\/p>\n\n\n\n
\n\n\n\n
Intuition and Approach (Optimal \u2013 Greedy)<\/h2>\n\n\n\n
The greedy approach works perfectly here because the Indian currency system is structured such that larger denominations are multiples of smaller ones.<\/p>\n\n\n\n
Why Greedy Works:<\/h3>\n\n\n\n