Another Coin Problem

The monetary system in ShadowLand is really simple and systematic. The locals only use coins.
The coins come in different values. The values used are:

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000, ...

Formally, for each K >= 0 there are coins worth 10K, and coins worth 25*100K.

Given an integer A denoting the cost of a car,
find and return the smallest number of coins necessary to pay exactly the cost of the car
(assuming you have a sufficient supply of coins of each of the types you will need).



Input Format

The only argument given is integer A.

Output Format

Return the smallest number of coins necessary to pay exactly the cost of the car.

Constraints

1 <= A <= 2*10^9

For Example

Input 1:
    A = 47
Output 1:
    5   (1 + 1 + 10 + 10 + 25)

Input 2:
    A = 9
Output 2:
    9   (1 * 9)
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Another Coin Problem on Interview Code Editor
Sign Up
to access hints and editorial solutions for Another Coin Problem

Discussion


Loading...
Click here to start solving coding interview questions