Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Use as many of the largest denomination as possible, then move to the next one.
  2. 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);
    }
}

Solve Minimum Coins (Greedy) online · All practice problems