Scale Engineer

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 <= 105
  • 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":

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

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

import java.math.BigInteger; class Solution {    public int minPartitions(String n) {        BigInteger num = new BigInteger(n);        int count = 0;        while (num.compareTo(BigInteger.ZERO) > 0) {            count++;            StringBuilder bStr = new StringBuilder();            String s = num.toString();            for (char c : s.toCharArray()) {                if (c > '0') {                    bStr.append('1');                } else {                    bStr.append('0');                }            }            BigInteger b = new BigInteger(bStr.toString());            num = num.subtract(b);        }        return count;    }}

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.

Solutions

class Solution {public  int minPartitions(String n) {    int ans = 0;    for (int i = 0; i < n.length(); ++i) {      ans = Math.max(ans, n.charAt(i) - '0');    }    return ans;  }}

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 →

Next problem