DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Minimum number of Coins

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.

problem statement: https://practice.geeksforgeeks.org/problems/-minimum-number-of-coins4426/1

Example 1:

Input: N = 43
Output: 20 20 2 1
Explaination: 
Minimum number of coins and notes needed 
to make 43. 
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: N = 1000
Output: 500 500
Explaination: minimum possible notes
is 2 notes of 500.
Enter fullscreen mode Exit fullscreen mode

Your Task:
You do not need to read input or print anything. Your task is to complete the function minPartition() which takes the value N as input parameter and returns a list of integers in decreasing order.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(N)

Solution:

The simple solution is done via a greedy algorithm.
Here we consider the maximum value of change required to settle the presented amount from the available denomination. This would go on until the change amount is adjusted with the change.

class Solution{
    static final int[] deno = new int[] {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000};

    static List<Integer> minPartition(int n) {
        List<Integer> res = new ArrayList<>();
        while(n > 0) {
            int d = getMaxDeno(n);

            // for better optimisation one could use division operation, 
            // but lets keep things simple
            n -= d;

            res.add(d);
        }
        return res;
    }

    static int getMaxDeno(int n) {
        if (n < deno[0]) // validity check
            throw new Exception("Invalid amount " + n + " is lesser than " + deno[0] );
        int index = Arrays.binarySearch(deno, n);
        if (index < 0) {
            index = - index - 2;
        }
        return deno[index];
    }
}
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay