# 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

## The math behind the problem

### Problem statement

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`

.

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

### Solution: Identify the maximum digit of `n`

Any digit `d`

can be obtained by summing the digit `1`

`d`

times.

The problem turns into identifying the maximum digit of `n`

.

#### Example 2

For `n = "82734"`

the answer is 8 because:

```
82734
= 11111
+ 11111
+ 10111
+ 10101
+ 10100
+ 10100
+ 10100
+ 10000
```

#### Code

```
#include <iostream>
using namespace std;
int minPartitions(string n) {
char maxDigit = '0';
for (char& d : n) {
maxDigit = max(maxDigit, d);
}
return maxDigit - '0';
}
int main() {
cout << minPartitions("32") << endl;
cout << minPartitions("82734") << endl;
cout << minPartitions("27346209830709182346") << endl;
}
```

```
Output:
3
8
9
```

#### Complexity

Runtime:

`O(N)`

, where`N = n.length`

.Extra space:

`O(1)`

.

### References

Â