A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.
Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.
Example 1:
Input: n = "32" Output: 3 Explanation: 10 + 11 + 11 = 32
Example 2:
Input: n = "82734" Output: 8
Example 3:
Input: n = "27346209830709182346" Output: 9
Constraints:
1 <= n.length <= 105n consists of only digits.n does not contain any leading zeros and represents a positive integer.Problem Overview: You are given a numeric string n. The task is to split it into the minimum number of deci-binary numbers (numbers containing only digits 0 or 1) such that their sum equals n. The result depends on how many 1s are required in each digit position across all constructed numbers.
Approach 1: Maximum Digit Evaluation (Greedy, O(n) time, O(1) space)
The key observation: every deci-binary number contributes at most 1 to each digit position. If a digit in n is d, you need at least d deci-binary numbers to sum to that position. Therefore, the minimum number of required deci-binary numbers equals the maximum digit present in the string. The algorithm simply iterates through the characters of the string, converts each digit, and tracks the maximum value seen. This greedy observation removes the need to explicitly construct the deci-binary numbers. The scan takes O(n) time and only a few variables, giving O(1) space.
This works because each resulting deci-binary number can contribute a 1 in positions where the original digit still needs value. Once you know the largest digit, you know how many parallel deci-binary layers are required to build the number.
Approach 2: Direct Conversion and Maximum (O(n) time, O(n) space)
This version first converts the numeric string into a list or array of integers, then scans the collection to find the maximum digit. Conceptually it follows the same greedy insight as the previous approach, but separates the parsing and evaluation steps. First iterate through the string and store each digit in an integer array. Then perform a second pass to compute the maximum element.
The algorithmic idea is identical: the maximum digit determines the minimum number of deci-binary numbers needed. However, this approach uses additional memory for the converted array, resulting in O(n) extra space. It can be useful in situations where the digits are reused for additional processing.
Both approaches rely on a simple greedy insight about digit contribution rather than constructing the numbers explicitly. Problems like this commonly appear in greedy and string processing categories, where scanning input once reveals the optimal answer.
Recommended for interviews: The Maximum Digit Evaluation approach. Interviewers expect you to recognize the greedy property quickly: the largest digit determines the number of required deci-binary layers. A brute-force construction approach would be unnecessarily complex, while identifying the max digit shows strong problem reduction and reasoning skills.
The key to solving this problem is understanding the relationship between the digits of the number and the deci-binary numbers. The minimum number of deci-binary numbers needed is dictated by the maximum digit in the string representation of the number. This is because to construct the number using deci-binary numbers (which only contain 0 and 1), at least one of these numbers must have a '1' in each digit position where the given number is non-zero. Each deci-binary number can only add 1 to each digit position.
In this C implementation, we iterate through the string of the number, keeping track of the maximum digit found. Since deci-binary numbers can only increment each position by 1, the maximum digit will determine the minimum number of such numbers required.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use a constant amount of extra space.
Instead of iterating through the string directly, an alternate way to solve the problem can be to map the string into an array of numbers first, then find the maximum in that array. However, this adds overhead without practical advantage, since the core of the solution relies on identifying the maximum digit in the string.
While this approach doesn't effectively differ in the outcome or complexity, it demonstrates the same maximum digit principle, emphasizing direct character handling in the number string.
Time Complexity: O(n), n being the length of the string.
Space Complexity: O(1).
The problem is equivalent to finding the maximum number in the string.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Maximum Digit Evaluation | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: Direct Conversion and Maximum | Time Complexity: O(n), n being the length of the string. |
| Quick Thinking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximum Digit Evaluation (Greedy) | O(n) | O(1) | Best general solution. Single pass over the string with constant space. |
| Direct Conversion and Maximum | O(n) | O(n) | Useful if digits must be reused later or stored for additional processing. |
Partitioning Into Minimum Number Of Deci-Binary Numbers | Brute Force | Trick | Leetcode 1689 | MIK • codestorywithMIK • 5,867 views views
Watch 9 more video solutions →Practice Partitioning Into Minimum Number Of Deci-Binary Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor