1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

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:

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

https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/

Get my FREE book "10 Classic Coding Challenges"

1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Comments

More from this blog

Leetcode 59. How To Go Around A Square Matrix In Spiral Order

Leetcode 120. How To Find The Minimum Path From Top To Bottom Of A Triangle

How To Find The Longest Substring Without Repeating Characters

How To Find The Maximal Subarray Having Distinct Elements

Common Mistakes in Coding Interviews and How to Avoid Them

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Identify the maximum digit of `n`

Example 2

Code

Complexity

References

Command Palette

Comments

More from this blog

Problem statement

Example 1

Example 2

Example 3

Constraints

Solution: Identify the maximum digit of n

Example 2

Code

Complexity

References

Solution: Identify the maximum digit of `n`