Partitioning Into Minimum Number of Deci-Binary Numbers: Find the Max Digit
Partitioning Into Minimum Number of Deci-Binary Numbers is LeetCode 1689. You are given a string n that represents a positive integer. You need to return the minimum number of positive deci-binary numbers that sum up to n.
A deci-binary number is one where every digit is either 0 or 1. For example, 101 and 1100 are deci-binary, but 112 and 23 are not. Your task is to figure out the fewest deci-binary numbers you can add together to produce the target number n.
The problem
You are working with numbers represented as strings (they can be very large). The goal is to express n as a sum of as few deci-binary numbers as possible. Each deci-binary number has digits restricted to 0 and 1.
For example, if n = "32", you could decompose it as 10 + 11 + 11 = 32. That uses 3 deci-binary numbers. Can you do it with fewer? No, and the reason comes down to a single digit.
The brute force approach
You might think about trying to enumerate all possible deci-binary partitions, subtracting deci-binary numbers one at a time and counting how many you need. But the space of deci-binary numbers grows exponentially with the number of digits, and the number of valid partitions is enormous. Even for a short string like "82734", trying all combinations is completely impractical.
The brute force approach also misses the point. This problem has a much cleaner structure hiding in the digits themselves.
The key insight
Think about what happens at a single digit position when you add deci-binary numbers together. Each deci-binary number contributes either 0 or 1 to that position. If you add k deci-binary numbers, the maximum value any single digit position can reach is k (when all k numbers contribute a 1 to that position).
Now flip this around. If the target number has a digit d in some position, you need at least d deci-binary numbers to produce that digit. No fewer will work, because each number adds at most 1 to that position.
The bottleneck is the largest digit in the string. If the largest digit is 9, you need at least 9 deci-binary numbers. If the largest digit is 3, you need at least 3.
And this lower bound is always achievable. With k deci-binary numbers (where k is the max digit), you can construct each one by setting its digit at position i to 1 if more contributions are still needed there, or 0 if that position is already satisfied. The greedy construction always works.
A deci-binary number contributes at most 1 to each digit position. The digit in n that requires the most contributions determines the minimum count. The answer is simply the largest digit in the string.
Step-by-step walkthrough
Let's trace through n = "32". The max digit is 3, so we need exactly 3 deci-binary numbers.
We can construct them greedily. For each deci-binary number, set a digit to 1 wherever the remaining target still has a nonzero digit:
- Deci-binary #1:
10. The tens digit needs more (3 remaining), the ones digit needs more (2 remaining). But we can be strategic. Pick10. Running total:10. Remaining:22. - Deci-binary #2:
11. Both digits still need contributions. Pick11. Running total:21. Remaining:11. - Deci-binary #3:
11. Both digits still need one more. Pick11. Running total:32. Done.
The walkthrough below shows this decomposition step by step.
Target: n = "32". Max digit is 3, so we need 3 deci-binary numbers.
We need to find 3 deci-binary numbers that sum to 32. Each has digits that are only 0 or 1.
Step 1: Add deci-binary number 10
Running total after 1 number: 10
Step 2: Add deci-binary number 11
Running total after 2 numbers: 21
Step 3: Add deci-binary number 11
Running total after 3 numbers: 32 = 32. Done!
The code
def minPartitions(n):
return int(max(n))
That is the entire solution. max(n) returns the largest character in the string (characters compare by their Unicode value, and digit characters '0' through '9' are in order). Converting to int gives you the numeric answer.
For example, max("82734") returns '8', and int('8') returns 8.
The entire solution is one line because the key insight reduces the problem completely. Once you see that each deci-binary number contributes at most 1 per digit, the answer is just the maximum digit. No loops, no data structures, no clever algorithms needed beyond that observation.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Find max digit | O(n) | O(1) |
Here n is the length of the string. The max() function scans every character once to find the largest, which takes linear time. No extra space is used beyond a single variable for the running maximum.
There is no slower practical approach worth discussing, because even understanding the problem leads directly to this solution. The "hard part" is the insight, not the implementation.
The building blocks
Per-digit contribution analysis
Many problems become easier when you analyze what happens at each digit position independently. In this problem, realizing that deci-binary digits are independent (each position can be 0 or 1 regardless of other positions) lets you reason about each digit in isolation. The same technique applies to problems involving binary representations, carry propagation, and bitwise operations.
Greedy lower bounds that are tight
Sometimes a lower bound argument also gives you a constructive upper bound. Here, the argument "you need at least max_digit numbers because one position requires that many contributions" is the lower bound. The construction "set digit to 1 wherever the remaining target is nonzero" proves the upper bound matches. When lower and upper bounds coincide, you have the exact answer with no gap to worry about.
This pattern appears in scheduling problems (minimum machines needed equals the maximum overlap), coloring problems (chromatic number equals the clique number in perfect graphs), and many other optimization settings.
Edge cases
- All digits are 1.
n = "111". The max digit is 1, so the answer is 1. The number itself is already deci-binary. - Single digit.
n = "9". The answer is 9. You need nine 1s. - All digits are 9.
n = "999". The answer is 9. You need 9 deci-binary numbers, each being111. - Contains zeros.
n = "10". The max digit is 1, so the answer is 1. The number 10 is itself deci-binary (digits are 1 and 0). - Very long string. The string can be up to 10^5 characters. The
max()scan is O(n), so performance is never an issue.
From understanding to recall
The key question to internalize is: "How much can each deci-binary number contribute to a single digit?" Once you see that the answer is "at most 1," everything follows. The minimum count equals the max digit because that is the tightest bottleneck across all positions.
Practice articulating why the max digit is both necessary (you cannot produce digit d with fewer than d contributions) and sufficient (you can always construct d deci-binary numbers that work). This two-sided reasoning, lower bound plus matching construction, is a fundamental proof technique in combinatorial optimization.
The next time you see a problem about decomposing a number into restricted components, ask yourself: what is the per-position contribution limit? That question often cracks the problem wide open.
Related posts
- Add Binary - Works with binary digit-by-digit addition, building comfort with per-digit reasoning.
- Add Strings - Digit-by-digit computation on string representations of numbers.
- Plus One - Another problem where digit-level analysis is the core technique.