Minimum number of Coins | Greedy Algorithm Solution

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

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.

Here’s the [Problem Link] to begin with.

Problem Statement – What Does the Problem Say?

You are given a value N. Your task is to represent this value using the minimum number of coins and notes available in the Indian currency system.

The available denominations are:

[2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]

You need to output the coins/notes used in making the change for the given amount.

Example 1:

Input: N = 43
Output: [20, 20, 2, 1]
Explanation: 
- 20 + 20 + 2 + 1 = 43 using 4 coins/notes.

Example 2:

Input: N = 1000
Output: [500, 500]
Explanation:
- The amount 1000 can be formed using only two 500 rupee notes.

The problem essentially asks: How can we represent the number with the least number of coins/notes possible?

Intuition and Approach (Optimal – Greedy)

The greedy approach works perfectly here because the Indian currency system is structured such that larger denominations are multiples of smaller ones.

Why Greedy Works:

• Always pick the largest denomination possible first.
• Subtract it from the total and repeat the process.
• Continue until the total reduces to zero.

This ensures that every step makes the most optimal choice, reducing the total quickly with fewer coins/notes.

Steps to Solve:

1. Maintain a list of available denominations sorted in descending order.
2. Start from the largest coin/note.
3. If the current denomination is less than or equal to the remaining total, pick it and subtract from the total.
4. Otherwise, move to the next smaller denomination.
5. Continue until the total becomes zero.

Code Implementation

Here’s the Python implementation of the optimal greedy solution with helpful comments:

class Solution:
    def minPartition(self, N):
        # Available denominations in Indian currency
        coins = [2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
        
        i = 0
        result = []
        total = N
        
        while total > 0:
            if total >= coins[i]:
                # Take the current coin/note
                result.append(coins[i])
                total = total - coins[i]
            else:
                # Move to the next smaller denomination
                i += 1
                
        return result

Code Explanation

• The array coins holds all the available denominations in descending order.
• A loop is run until the total becomes zero.
• At each step, we check if the current coin/note can fit into the remaining total.
  • If yes, add it to the result list and subtract it from the total.
  • If no, move to the next smaller denomination.
• This process guarantees that we always use the least number of coins/notes possible.

For example, if N = 43:

• Start with 20 → total reduces to 23.
• Again take 20 → total reduces to 3.
• Take 2 → total reduces to 1.
• Take 1 → total becomes 0.
  Result = [20, 20, 2, 1].

Time and Space Complexity

• Time Complexity:
  • At most, we go through all denominations for every subtraction.
  • In practice, the loop runs a small number of times since large denominations reduce the total quickly.
  • O(N/denomination) in worst case, but effectively O(k) where k = number of coins (since denominations are fixed, it is constant).
  • Simplified: O(1) for practical purposes.
• Space Complexity:
  • We store the result list containing the selected coins/notes.
  • In the worst case, this could be proportional to N (if N = 1 repeated many times), but generally small.
  • O(k) where k = number of selected coins.

Conclusion

The Minimum Number of Coins problem is a straightforward application of the Greedy Algorithm. By always selecting the largest possible denomination at each step, we ensure that the number of coins and notes used is minimized.

This approach is highly efficient, works in constant time for practical purposes, and is a perfect example of how greedy strategies provide optimal solutions in currency-based systems.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.