LeetCode 1689 - Partitioning Into Minimum Number Of Deci-Binary Numbers

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

Problem Understanding

The problem asks us to determine the minimum number of positive deci-binary numbers required to sum up to a given decimal number represented as a string.

A deci-binary number is a number whose digits consist only of 0 and 1, and it cannot contain leading zeros. For example:

101 is valid because every digit is either 0 or 1
1100 is valid
112 is invalid because it contains a 2
3001 is invalid because it contains a 3

We are given a string n representing a positive decimal integer. The goal is to return the smallest number of deci-binary numbers whose sum equals n.

To understand the problem better, consider the input "32".

We want to construct the number 32 by adding together deci-binary numbers. One valid decomposition is:

This uses 3 deci-binary numbers, and it turns out to be the minimum possible answer.

The key detail is that we are not asked to construct the actual deci-binary numbers. We only need to compute the minimum count.

Understanding the Constraints

The constraints are:

1 <= n.length <= 10^5
n contains only digits
n has no leading zeros
n represents a positive integer

The most important observation here is the length limit. Since n can contain up to 100,000 digits, converting it into an integer may not even fit into standard numeric types. More importantly, any solution that performs expensive repeated operations or simulations will likely be too slow.

We need a solution that runs in linear time, or close to it.

Important Edge Cases

Several inputs can trip up naive implementations.

If the number contains only 1s, such as "1111", the answer is simply 1, since the number itself is already deci-binary.

If the number contains a large digit such as 9, for example "27346209830709182346", the answer must be at least 9, because no single deci-binary number can contribute more than 1 to any digit position.

Single-digit inputs are also important. For "7", the answer is 7, because we would need seven 1s stacked together to create the digit 7.

The problem guarantees that the input is valid, positive, and contains no leading zeros, so we do not need to handle malformed input.

Approaches

Brute Force Approach

A brute-force approach would attempt to repeatedly construct deci-binary numbers and subtract them from n until the remaining value becomes zero.

For example, given "82734", we might repeatedly create a deci-binary number by placing 1s in positions where digits are nonzero:

82734
11111
-----
71623
11111
-----
60512
...

We continue subtracting until all digits become zero.

This approach eventually produces the correct result because each subtraction reduces every nonzero digit by at most 1, and eventually the number becomes zero.

However, it is inefficient. In the worst case, such as "999999999", we would need to perform up to 9 full traversals of the string. While 9 is technically constant, simulating the subtraction process is unnecessary work and makes the logic more complicated.

We can do better by recognizing a mathematical property of the problem.

Key Insight

The crucial observation is that the answer is simply the maximum digit in the string.

Why?

Each deci-binary number can contribute at most 1 to any digit position. Suppose one digit in n is 8.

That means the sum of all deci-binary numbers must contribute a total of 8 in that position. Since each deci-binary number contributes at most 1, we need at least 8 numbers.

Now consider whether 8 numbers are always sufficient.

Yes. We can imagine stacking deci-binary numbers so that each digit position receives exactly the required number of 1s.

For example:

The largest digit is 8.

We can construct 8 deci-binary numbers so that:

The first digit gets eight 1s
The second digit gets two 1s
The third digit gets seven 1s
And so on

Since every digit can be satisfied independently, the maximum digit determines both:

The minimum number required
A sufficient number to construct the sum

Therefore, the problem reduces to finding the largest digit in the string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(9 × n) = O(n)	O(n)	Simulates repeated subtraction of deci-binary numbers
Optimal	O(n)	O(1)	Find the maximum digit in the string

Algorithm Walkthrough

Optimal Algorithm

Initialize a variable to track the maximum digit seen so far.
Traverse each character in the string n.
Convert the current character into its numeric value.
Compare the current digit with the running maximum. If the digit is larger, update the maximum.
Since digits only range from 0 to 9, if we ever encounter 9, we can immediately return 9, because no larger answer is possible.
After scanning the entire string, return the maximum digit found.

Why it works

The correctness comes from a simple invariant.

For any digit position, each deci-binary number contributes at most 1. Therefore, if a digit equals d, we need at least d numbers to produce that digit.

At the same time, maxDigit numbers are always sufficient because we can distribute 1s across the digit positions to exactly match every required digit count.

Thus, the minimum number of deci-binary numbers equals the largest digit in n.

Python Solution

class Solution:
    def minPartitions(self, n: str) -> int:
        max_digit = 0

        for digit_char in n:
            digit = int(digit_char)
            max_digit = max(max_digit, digit)

            if max_digit == 9:
                return 9

        return max_digit

Implementation Explanation

The implementation maintains a variable called max_digit, which stores the largest digit encountered so far.

We iterate through each character in the string n. Since the input is a string, each digit arrives as a character, so we convert it into an integer using int().

After conversion, we compare it with the current maximum and update accordingly.

An optimization is included: if we encounter 9, we immediately return 9. Since digits range only from 0 to 9, no larger answer can exist.

Finally, if no 9 is found, we return the largest digit seen during traversal.

The implementation directly follows the mathematical insight discussed earlier.

Go Solution

func minPartitions(n string) int {
    maxDigit := 0

    for _, char := range n {
        digit := int(char - '0')

        if digit > maxDigit {
            maxDigit = digit
        }

        if maxDigit == 9 {
            return 9
        }
    }

    return maxDigit
}

Go-Specific Implementation Differences

The Go solution is very similar to the Python version, but there are a few implementation details worth noting.

In Go, iterating over a string produces Unicode rune values. Since the input consists only of digits, subtracting '0' converts a character like '7' into the integer 7.

Unlike Python, Go does not have a built-in max() function for integers, so we perform a manual comparison.

There is no concern about integer overflow because digits are limited to the range 0 through 9.

Worked Examples

Example 1

Input: n = "32"

We scan the string and track the largest digit.

Step	Character	Digit	max_digit
1	`'3'`	3	3
2	`'2'`	2	3

Final answer:

Why?

The digit 3 means we need at least 3 deci-binary numbers.

One valid construction is:

Example 2

Input: n = "82734"

Step	Character	Digit	max_digit
1	`'8'`	8	8
2	`'2'`	2	8
3	`'7'`	7	8
4	`'3'`	3	8
5	`'4'`	4	8

Final answer:

The largest digit is 8, so we need exactly 8 deci-binary numbers.

Example 3

Input: n = "27346209830709182346"

Step	Character	Digit	max_digit
1	`'2'`	2	2
2	`'7'`	7	7
3	`'3'`	3	7
4	`'4'`	4	7
5	`'6'`	6	7
6	`'2'`	2	7
7	`'0'`	0	7
8	`'9'`	9	9

At this point, we can immediately stop and return 9, because no digit can exceed 9.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan each digit exactly once
Space	O(1)	Only a single variable is used

The algorithm performs one pass through the input string, making the runtime proportional to the number of digits. Since we only store a few integer variables regardless of input size, the extra memory usage remains constant.

The early return optimization for digit 9 can reduce runtime in practice, but the worst-case complexity remains linear.

Test Cases

solution = Solution()

# Provided examples
assert solution.minPartitions("32") == 3  # Basic example
assert solution.minPartitions("82734") == 8  # Largest digit in middle
assert solution.minPartitions("27346209830709182346") == 9  # Early stop on 9

# Single digit inputs
assert solution.minPartitions("1") == 1  # Smallest valid input
assert solution.minPartitions("7") == 7  # Single large digit
assert solution.minPartitions("9") == 9  # Maximum possible answer

# All same digits
assert solution.minPartitions("11111") == 1  # Already deci-binary
assert solution.minPartitions("55555") == 5  # Uniform digits
assert solution.minPartitions("99999") == 9  # Maximum repeated digit

# Mixed digits
assert solution.minPartitions("101010") == 1  # Only 0s and 1s
assert solution.minPartitions("24680") == 8  # Largest even digit
assert solution.minPartitions("9081726354") == 9  # Largest digit at start

# Large input stress case
assert solution.minPartitions("1" * 100000) == 1  # Maximum length input
assert solution.minPartitions("8" * 100000) == 8  # Large repeated digit

Test	Why
`"32"`	Verifies the first provided example
`"82734"`	Ensures maximum digit determines answer
`"27346209830709182346"`	Tests early termination on `9`
`"1"`	Smallest valid input
`"7"`	Single large digit
`"9"`	Maximum possible digit
`"11111"`	Already deci-binary
`"55555"`	Uniform repeated digit
`"99999"`	Repeated maximum digit
`"101010"`	Contains only `0` and `1`
`"24680"`	Largest digit appears at end
`"9081726354"`	Largest digit appears at start
`"1" * 100000`	Maximum input size
`"8" * 100000`	Stress test for large repeated values

Edge Cases

Input Contains Only `0` and `1` Digits

An input like "10101" is already representable using a single deci-binary number. A naive implementation might overcomplicate the decomposition process, but our solution simply finds the maximum digit, which is 1, and correctly returns 1.

Single-Digit Inputs

For inputs such as "7", there is only one digit to examine. Since a deci-binary number can contribute at most 1 at a digit position, we need exactly 7 numbers. The implementation naturally handles this because the maximum digit becomes the answer.

Presence of `9`

If the input contains 9, such as "27346209830709182346", the answer must be 9, since no digit can exceed 9. This case is important because it allows an early exit optimization. The implementation immediately returns 9 upon seeing it, avoiding unnecessary work on very long strings.

Very Large Inputs

The input length can reach 100,000 characters. Any approach that repeatedly simulates subtraction or builds intermediate representations could become inefficient. Our implementation performs only a single pass over the string and uses constant extra memory, making it efficient even at maximum input size.

LeetCode 1689 - Partitioning Into Minimum Number Of Deci-Binary Numbers

Solution

Problem Understanding

Understanding the Constraints

Important Edge Cases

Approaches

Brute Force Approach

Key Insight

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Implementation Explanation

Go Solution

Go-Specific Implementation Differences

Worked Examples

Example 1

Example 2

Example 3

Complexity Analysis

Test Cases

Edge Cases

Input Contains Only 0 and 1 Digits

Single-Digit Inputs

Presence of 9

Very Large Inputs

Input Contains Only `0` and `1` Digits

Presence of `9`