problemmediumalgorithmsleetcode-1689leetcode 1689leetcode1689

Partitioning Into Minimum Number Of Deci-Binary Numbers

MediumUpdated: Aug 1, 2025
Practice on:
LeetCode

Problem

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

Solution

Method 1 – Maximum Digit Greedy

Intuition

Each deci-binary number can only contribute 1 to each digit position (since its digits are only 0 or 1). To form a digit d in any position, we need at least d deci-binary numbers stacked so that their sum at that position is d. Therefore, the minimum number of deci-binary numbers needed is equal to the largest digit in n.

Approach

  1. Scan through all digits of n.
  2. Find the maximum digit (let's call it x).
  3. The answer is x, because you need at least x deci-binary numbers to sum up to n at the position where n has digit x.

Example (Step by Step Construction):

Let n = "135". The digits are 1, 3, 5, so the maximum is 5. We need 5 deci-binary numbers, each of length 3:

a1 = 000
a2 = 000
a3 = 000
a4 = 000
a5 = 000

Now, for each digit position:

  • For the first digit (1): fill the first 1 number with 1 at position 1:
    • a1 = 1__
  • For the second digit (3): fill the first 3 numbers with 1 at position 2:
    • a1 = 11_
    • a2 = 01_
    • a3 = 01_
  • For the third digit (5): fill the first 5 numbers with 1 at position 3:
    • a1 = 111
    • a2 = 011
    • a3 = 011
    • a4 = 001
    • a5 = 001

So the five deci-binary numbers are:

a1 = 111
a2 = 011
a3 = 011
a4 = 001
a5 = 001

Their sum is 111 + 11 + 11 + 1 + 1 = 135.

Visual proof: Visual 1 Visual 2

Code

C++
class Solution {
public:
    int minPartitions(string n) {
        char max_digit = '0';
        for (char c : n) {
            if (c > max_digit) max_digit = c;
        }
        return max_digit - '0';
    }
};
Go
func minPartitions(n string) int {
    maxDigit := '0'
    for _, c := range n {
        if c > maxDigit {
            maxDigit = c
        }
    }
    return int(maxDigit - '0')
}
Java
class Solution {
    public int minPartitions(String n) {
        char maxDigit = '0';
        for (char c : n.toCharArray()) {
            if (c > maxDigit) maxDigit = c;
        }
        return maxDigit - '0';
    }
}
Kotlin
class Solution {
    fun minPartitions(n: String): Int {
        var maxDigit = '0'
        for (c in n) {
            if (c > maxDigit) maxDigit = c
        }
        return maxDigit - '0'
    }
}
Python
class Solution:
    def minPartitions(self, n: str) -> int:
        return int(max(n))
Rust
impl Solution {
    pub fn min_partitions(n: String) -> i32 {
        n.chars().map(|c| c.to_digit(10).unwrap()).max().unwrap() as i32
    }
}
TypeScript
class Solution {
    minPartitions(n: string): number {
        let maxDigit = '0';
        for (const c of n) {
            if (c > maxDigit) maxDigit = c;
        }
        return Number(maxDigit);
    }
}

Complexity

  • ⏰ Time complexity: O(L), where L is the length of n. We scan each digit once to find the maximum.
  • 🧺 Space complexity: O(1), since we only use a constant number of variables.

Comments