Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
Tags: algorithms, javascript, java, python
Published: 2021-05-26 10:40:38

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/discuss/1231505).*

---

#### [Leetcode Problem #1689 (*Medium*): Partitioning Into Minimum Number Of Deci-Binary Numbers](https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:
![Visual 1](https://i.imgur.com/rn13iSv.png)
Then we can think of a graph as a stack of numbers to be added:
![Visual 2](https://i.imgur.com/0CqWfzM.png)
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
const minPartitions = n => Math.max(...n.split(''))
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def minPartitions(self, n: str) -> int:
        return max(n)
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int minPartitions(string n) {
        char best = '0';
        for (auto& c : n)
            if (c > best) best = c;
        return best - '0';
    }
};
```