Minimize coins with overpay and change

Q: Minimize coins with overpay and change

This question evaluates algorithmic optimization and combinatorial reasoning in the coin-change domain, measuring proficiency with efficient numeric manipulation, counting strategies, and handling of fixed coin denominations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You have an unlimited number of coins with denominations:

1, 5, 10, 50, 100, 200

You need to pay exactly n units to another person. You are allowed to overpay, and the other person will always be able to give you exact change (they also have unlimited coins).

Define the total coins used as:

the number of coins you give to pay, plus
the number of coins you receive back as change.

Return the minimum possible total number of coins needed to complete the transaction.

Input

A single integer n .

Output

A single integer: the minimum total number of coins exchanged.

Example

Input:

Output:

Explanation: Pay 50 + 1 (2 coins) and receive 10 as change (1 coin), total 2 + 1 = 3.

Constraints

Assume 0 ≤ n ≤ 10^9 .
Both payer and receiver have unlimited coins of each denomination.

Minimize coins with overpay and change

Quick Overview

Input

Output

Example

Constraints

Comments (0)