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.
Example 2:
Input: N = 1000
Output: 500 500
Explaination: minimum possible notes
is 2 notes of 500.
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];
}
}
Top comments (0)