Partitioning Into Minimum Number Of Deci-Binary Numbers

Med

#1549Time: O(K * L), where L is the length of the string `n` and K is the value of the largest digit in `n`. Since K is at most 9, the complexity is effectively O(L). However, operations on large numbers (like `BigInteger`) have a higher constant factor than simple character comparison.Space: O(L) to store the intermediate number representation (e.g., `BigInteger` or a character array for subtraction), where L is the length of the string n.1 company

Patterns

Greedy

Data structures

String

Companies

Nutanix

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the partitioning process by repeatedly subtracting a specially constructed deci-binary number from n until n becomes zero. The total number of subtractions gives the answer.

Algorithm

Initialize a counter count to 0.
Convert the input string n into a large number representation (e.g., BigInteger).
Start a loop that continues as long as the number is greater than 0.
Inside the loop:
- Increment count.
- Construct a deci-binary number string by iterating through the digits of the current number. If a digit is non-zero, append '1'; otherwise, append '0'.
- Convert this deci-binary string to a large number.
- Subtract this deci-binary number from the current number.
After the loop terminates, return count.

Walkthrough

The core idea is based on a greedy strategy. In each step, we subtract a deci-binary number formed by placing a '1' at every position where the corresponding digit of the current number n is non-zero. This process is repeated until n becomes 0. The number of iterations is the result.

For example, with n = "32":

count = 0, num = 32.
Iteration 1: num > 0. count becomes 1. The deci-binary to subtract is 11. num becomes 32 - 11 = 21.
Iteration 2: num > 0. count becomes 2. The deci-binary to subtract is 11. num becomes 21 - 11 = 10.
Iteration 3: num > 0. count becomes 3. The deci-binary to subtract is 10. num becomes 10 - 10 = 0.
num is 0, loop terminates. Return count = 3.

This requires handling large number arithmetic, which can be done using Java's BigInteger class.

1import java.math.BigInteger;2 3class Solution {4    public int minPartitions(String n) {5        BigInteger num = new BigInteger(n);6        int count = 0;7        while (num.compareTo(BigInteger.ZERO) > 0) {8            count++;9            StringBuilder bStr = new StringBuilder();10            String s = num.toString();11            for (char c : s.toCharArray()) {12                if (c > '0') {13                    bStr.append('1');14                } else {15                    bStr.append('0');16                }17            }18            BigInteger b = new BigInteger(bStr.toString());19            num = num.subtract(b);20        }21        return count;22    }23}

Complexity

Time

O(K * L), where L is the length of the string `n` and K is the value of the largest digit in `n`. Since K is at most 9, the complexity is effectively O(L). However, operations on large numbers (like `BigInteger`) have a higher constant factor than simple character comparison.

Space

O(L) to store the intermediate number representation (e.g., `BigInteger` or a character array for subtraction), where L is the length of the string n.

Trade-offs

Pros

It's a conceptually straightforward simulation of the process.
Correctly arrives at the minimum number.

Cons

Less efficient than the optimal solution due to repeated operations on large numbers.
Implementation can be complex if not using a library like BigInteger.

A highly efficient approach based on the insight that the minimum number of deci-binary numbers required is simply equal to the largest digit present in the input string n.

Algorithm

Initialize a variable max_digit to 0.
Iterate through each character c of the input string n.
Convert the character c to its integer equivalent d.
If d is greater than max_digit, update max_digit to d.
After iterating through all characters, return max_digit.

Walkthrough

The problem can be simplified by analyzing the sum at each place value. Let k be the number of deci-binary numbers. When summing these k numbers, the sum of digits at any column is at most k (since each digit is 0 or 1). This sum must be sufficient to form the corresponding digit in n (considering carries).

This implies that k must be at least as large as the largest digit in n. Let this be max_digit. So, k >= max_digit.

Furthermore, we can always construct a solution with k = max_digit numbers. We can define max_digit deci-binary numbers where the j-th number (for j from 1 to max_digit) has a '1' at position i if the i-th digit of n is greater than or equal to j, and '0' otherwise. The sum of these numbers, without any carries, equals n.

For example, for n = "32", max_digit = 3. We need 3 numbers:

b1 (for digits >= 1): 11
b2 (for digits >= 2): 11
b3 (for digits >= 3): 10 Sum = 11 + 11 + 10 = 32.

Therefore, the problem reduces to finding the maximum digit in the string.

1class Solution {2    public int minPartitions(String n) {3        int maxDigit = 0;4        for (int i = 0; i < n.length(); i++) {5            int digit = n.charAt(i) - '0';6            if (digit > maxDigit) {7                maxDigit = digit;8            }9            // An early exit optimization10            if (maxDigit == 9) {11                return 9;12            }13        }14        return maxDigit;15    }16}

Complexity

Time

O(L), where L is the length of the string `n`. We only need a single pass through the string.

Space

O(1), as we only need a single variable to keep track of the maximum digit found so far.

Trade-offs

Pros

Extremely efficient with linear time and constant space complexity.
Very simple to implement.
Solves the problem directly by identifying the core constraint.

Cons

The mathematical proof for why this simple approach works is non-trivial and not immediately obvious.

Solutions

Solution

1class Solution {2public3  int minPartitions(String n) {4    int ans = 0;5    for (int i = 0; i < n.length(); ++i) {6      ans = Math.max(ans, n.charAt(i) - '0');7    }8    return ans;9  }10}

1class Solution {2public:3  int minPartitions(string n) {4    int ans = 0;5    for (char &c : n)6      ans = max(ans, c - '0');7    return ans;8  }9};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem