Removing digits
Given an integer
n, you are asked to calculate the minimum number of steps that would be required to get from n to 0. On each step, you are allowed to subtract one of the digits from the number.Input
The input contains a single integer
n (1 ≤ n ≤ ).Output
The program should print the minimum number of steps we should take to get from
n to 0.Examples
Input | Output |
9 | 1 |
11 | 3 |
27 | 5 |
Explanation
- 9 → 0 ⇒ 1 step
- 11 → 10 → 9 → 0 ⇒ 3 steps
- 27 → 20 → 18 → 10 → 9 → 0 ⇒ 5 steps
Constraints
Time limit: 12 seconds
Memory limit: 512 MB
Output limit: 1 MB