{ }codelper
greedyinteger divisionP0041

Fewest coins

You have unlimited coins of 500, 100, 50 and 10 won.
Print the minimum number of coins needed to make exactly n won.

Input
10 ≤ n ≤ 1,000,000,000, and n is a multiple of 10.
Output
The minimum number of coins
Example 1 · stdin
1880
stdout
10
Example 2 · stdin
40
stdout
4
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Greedy: use as many of the largest coin as fit (the quotient), then move on with the remainder.
Here each coin is a multiple of the next smaller one (500 = 5×100, 100 = 2×50, 50 = 5×10), which guarantees greedy is optimal; with coins 10, 40 and 50 it fails, since 80 = 40+40 (2 coins) beats 50+10+10+10 (4).
The language difference is division: int / int in C, C++, Java and C#, and Python's //, give the quotient, but / in JavaScript and TypeScript gives decimals (1880 / 500 = 3.76), so you need Math.floor.
Craykon's / also gives decimals, so use Mathf.Quot(n, coin); the remainder is % everywhere.
Order matters too: starting from the smallest coin uses only 10-won coins.

Pythonmain.py · 6 lines
n = int(input())count = 0for coin in [500, 100, 50, 10]:    count += n // coin    n %= coinprint(count)
JavaScriptmain.js · 7 lines
let n = Number(require("fs").readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) {  count += Math.floor(n / coin);  n %= coin;}console.log(count);
TypeScriptmain.ts · 8 lines
import { readFileSync } from "node:fs";let n: number = Number(readFileSync(0, "utf8").trim());let count = 0;for (const coin of [500, 100, 50, 10]) {  count += Math.floor(n / coin);  n %= coin;}console.log(count);
JavaMain.java · 13 lines
import java.util.Scanner; public class Main {    public static void main(String[] args) {        int n = new Scanner(System.in).nextInt();        int count = 0;        for (int coin : new int[] {500, 100, 50, 10}) {            count += n / coin;            n %= coin;        }        System.out.println(count);    }}
C#Main.cs · 16 lines
using System; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        int count = 0;        foreach (int coin in new[] { 500, 100, 50, 10 })        {            count += n / coin;            n %= coin;        }        Console.WriteLine(count);    }}
C++main.cpp · 11 lines
#include <iostream> int main() {    int n, count = 0;    std::cin >> n;    for (int coin : {500, 100, 50, 10}) {        count += n / coin;        n %= coin;    }    std::cout << count << '\n';}
Cmain.c · 13 lines
#include <stdio.h> int main(void) {    int n, count = 0;    const int coins[] = {500, 100, 50, 10};    scanf("%d", &n);    for (int i = 0; i < 4; i++) {        count += n / coins[i];        n %= coins[i];    }    printf("%d\n", count);    return 0;}
Craykonmain.cray · 8 lines
n = Console.ReadLine().ToNumber();count = 0;foreach (coin in [500, 100, 50, 10]){    count += Mathf.Quot(n, coin);    n = n % coin;}Console.WriteLine(count);