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

####
Leetcode Problem #1689 (*Medium*): Partitioning Into Minimum Number Of Deci-Binary Numbers

####
*Description:*

*Description:*

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

A decimal number is called

deci-binaryif 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 positivedeci-binarynumbers needed so that they sum up to`n`

.

####
*Examples:*

*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:*

*Constraints:*

`1 <= n.length <= 10^5`

`n`

consists of only digits.`n`

does not contain any leading zeros and represents a positive integer.

####
*Idea:*

*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:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
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:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

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

## Top comments (0)