Practice › Greedy
Minimum Coins (Greedy)
Easy · Greedy · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Indian currency has denominations 1, 2, 5, 10, 20, 50, 100, 200, 500 and 2000, with unlimited supply. Print the minimum number of coins/notes that add up to exactly V.
Input
A single integer V.
Output
The minimum number of coins/notes.
Constraints
- 1 ≤ V ≤ 10^9
For this currency system, always taking the largest denomination that fits is optimal. (That is not true for every coin system — then you need DP.)
Example 1
Input
49
Output
5
Example 2
Input
121
Output
3
Hints
- Use as many of the largest denomination as possible, then move to the next one.
- V / d gives how many of denomination d to take, and V % d is what is left.
Approach
For a canonical coin system like Indian currency, the greedy choice (largest note that fits) is always optimal. Walk the denominations from 2000 down to 1: add V / d to the count and keep V % d. With denominations such as {1, 3, 4} greedy fails (6 = 3 + 3, but greedy gives 4 + 1 + 1) — that is when you need the coin-change DP.
Complexity: O(number of denominations) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long v;
cin >> v;
long long count = 0;
for (long long d : {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1}) {
count += v / d;
v %= d;
}
cout << count << "\n";
return 0;
}Python solution
v = int(input())
count = 0
for d in (2000, 500, 200, 100, 50, 20, 10, 5, 2, 1):
count += v // d
v %= d
print(count)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
long v = new Scanner(System.in).nextLong(), count = 0;
for (long d : new long[] {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1}) {
count += v / d;
v %= d;
}
System.out.println(count);
}
}