We’re preparing your current view and syncing the latest data.
Minimum Deci-Binary Numbers Partition
gfgA deci-binary number is a number consisting only of digits 0 or 1, and no leading zeros unless the number is 0 itself. Given a string n representing a decimal number, you are asked to determine the minimum number of deci-binary numbers needed so that their sum equals n. For example, n = "32" can be decomposed into "11" + "11" + "10". The minimum number of deci-binary numbers in this case is 3.
A single line containing the decimal number n as a string.
An integer representing the minimum number of deci-binary numbers needed to sum to n.
1 <= n.length <= 10^5 n consists of digits only. n does not contain leading zeros except for the number zero itself.
Example 1
Input
32
Output
3
Explanation
The number 32 can be split into deci-binary numbers: 11 + 11 + 10.
Example 2
Input
82734
Output
8
Explanation
The maximum digit is 8, so minimum 8 deci-binary numbers are needed.
Example 3
Input
27346209830709182346
Output
9
Explanation
The maximum digit is 9, so minimum 9 deci-binary numbers are needed.