Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers

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:

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

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:

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

(Jump to: Problem Description || Solution Idea)

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

---

Python Code:

(Jump to: Problem Description || Solution Idea)

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

---

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:

(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';
    }
};