Find the minimum number of deci-binary numbers needed so their sum equals a given decimal string.
Problem
You are given a positive decimal number as a string n. A deci-binary number is a positive integer whose decimal digits are only 0 or 1.
You may choose any number of deci-binary numbers and add them together. Your task is to determine the minimum number of deci-binary numbers required so that their sum is exactly n.
Because n can be very large, it is provided as a string instead of an integer.
Key idea
Each digit of n must be formed by stacking 1s from several deci-binary numbers. The answer is determined by the largest digit appearing in n.
Input Format
- A single string
nrepresenting a positive integer without leading zeros.
Output Format
- Return the minimum count of deci-binary numbers whose sum is
n.
Constraints
1 <= n.length <= $10^{5}$ncontains only characters from'0'to'9'nhas no leading zeros
Hints
- Think about one decimal place at a time.
- What is the minimum number of
1s needed to build the largest digit in the string? - You do not need to simulate addition across many numbers.
Input Format
n: a decimal string representing a positive integer.
Output Format
- An integer: the minimum number of deci-binary numbers needed to sum to
n.
Constraints
1 <= n.length <= $10^{5}$ncontains only digits0-9nhas no leading zeros
Example 1
Input
n = "32"
Output
3
Explanation
One optimal decomposition is 11 + 11 + 10 = 32. Since the largest digit is 3, at least 3 deci-binary numbers are needed.
Example 2
Input
n = "82734"
Output
8
Explanation
The largest digit is 8, so 8 deci-binary numbers are necessary and sufficient.
Show 1 more example
Example 3
Input
n = "27346209830709182346"
Output
9
Explanation
The maximum digit in the string is 9, so the answer is 9.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.