seanpgallivan

Posted on

# Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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`.

#### Examples:

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 <= 10^5`
• `n` consists of only digits.
• `n` does not contain any leading zeros and represents a positive integer.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

If each deci-binary number has no higher than a 1 in each position, then it will take at least x numbers to achieve an x in any given position of n. This means that the largest character in any position in n will determine how many deci-binary numbers must be added together to obtain n.

For visual proof, we can think of n as a graph of its digits:

Then we can think of a graph as a stack of numbers to be added:

This stack must necessarily then be as tall as the largest single digit in n.

We can quite easily separate the characters of n, find the max, and return that number.

• Time Complexity: O(N) where N is the length of the input string n
• Space Complexity: O(N) or O(1) depending on whether or not we split n to an array first

#### Javascript Code:

``````const minPartitions = n => Math.max(...n.split(''))
``````

#### Python Code:

``````class Solution:
def minPartitions(self, n: str) -> int:
return max(n)
``````

#### Java Code:

``````class Solution {
public int minPartitions(String n) {
char best = '0';
for (char c : n.toCharArray())
if (c > best) best = c;
return best - '0';
}
}
``````

#### C++ Code:

``````class Solution {