Challenge: Fewest Notes

Lab Java Beginner 10 points

Pay an amount with the fewest notes and coins from 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1 using the greedy method. For each value actually used, biggest first, print value x count, then total: k.

Input

One whole number, the amount (1 ≤ amount ≤ 10⁹).

Output

One line per value used, then the total number of pieces.

Example

Input

Output

2000 x 1
500 x 1
200 x 1
50 x 1
20 x 1
10 x 1
5 x 1
2 x 2
total: 9

Sample input available Sample output available

Editor

Java

Hints

Go from the biggest note to the smallest.

amount / note tells you how many fit at once – no need for a loop that subtracts one at a time.

Solution explanation

With this note system greedy is always optimal. Using division makes it O(number of note values), even for a billion.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int amount = sc.nextInt();
        int[] notes = {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1};
        int total = 0;
        StringBuilder sb = new StringBuilder();
        for (int note : notes) {
            int count = amount / note;        // how many of this note fit
            if (count > 0) {
                sb.append(note).append(" x ").append(count).append('\n');
                amount -= count * note;
                total += count;
            }
        }
        sb.append("total: ").append(total);
        System.out.println(sb);
    }
}

Output

Answer