Posts Minimum number of Coins (geeksforgeeks - SDE Sheet)
Post
Cancel

Minimum number of Coins (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given an infinite supply of each denomination of Indian currency { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } and a target value N. Find the minimum number of coins and/or notes needed to make the change for Rs N. You must return the list containing the value of coins required.

geeksforgeeks

SOLUTION

We can solve this by using a greedy approach. The idea is to use the largest possible coin first to reduce the amount N as quickly as possible. We have an array of coin denominations sorted in descending order. Starting from the largest coin, we repeatedly subtract the coin’s value from N and add that coin to the result list. If a coin is too large to fit into N, we move to the next smaller denomination. This process continues until N becomes zero, and the list of coins used to make the amount is returned.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    static List<Integer> minPartition(int N) {

        int[] coins = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};

        // List to store the selected coins
        List<Integer> list = new ArrayList<>();

        // Index to track which denomination we're currently considering
        int idx = 0;

        // While we haven't finished breaking down the amount N and haven't exhausted all denominations
        while (N > 0 && idx < coins.length) {

            // If the current denomination can fit into the remaining amount N
            if (coins[idx] <= N) {

                // Add the current denomination to the list
                list.add(coins[idx]);

                // Subtract the value of the current coin from N
                N -= coins[idx];

            } else {

                // Move to the next smaller denomination
                idx++;

            }
        }

        return list;
    }

}
This post is licensed under CC BY 4.0 by the author.