Follow

Follow

# C++ Solution to Coding Challenge 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

## The math behind the problem

Nhut Nguyen
Â·Oct 17, 2022Â·

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

Get my FREE book "10 Classic Coding Challenges"