Partitioning Into Minimum Number Of Deci-Binary Numbers | May LeetCoding Challenge 2021

Here is the description of the problem I come across today.

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 <= 105
• n consists of only digits.
• n does not contain any leading zeros and represents a positive integer.

Idea

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

Java Code:

Problem Description

class Solution {
    public int minPartitions(String n) {
        char best = '0';
        for (char c : n.toCharArray())
            if (c > best) best = c;
        return best - '0';
    }
}