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:

1
2
3
4
5

Input:
n = "32"
Output:
 3
Explanation: 10 + 11 + 11 = 32

Example 2:

1
2
3
4

Input:
n = "82734"
Output:
 8

Example 3:

1
2
3
4

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:

1
2
3
4
5

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:

1
2
3
4
5

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

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

Visual proof:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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';
    }
};
1
2
3
4
5
6
7
8
9

func minPartitions(n string) int {
    maxDigit := '0'
    for _, c := range n {
        if c > maxDigit {
            maxDigit = c
        }
    }
    return int(maxDigit - '0')
}
1
2
3
4
5
6
7
8
9

class Solution {
    public int minPartitions(String n) {
        char maxDigit = '0';
        for (char c : n.toCharArray()) {
            if (c > maxDigit) maxDigit = c;
        }
        return maxDigit - '0';
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun minPartitions(n: String): Int {
        var maxDigit = '0'
        for (c in n) {
            if (c > maxDigit) maxDigit = c
        }
        return maxDigit - '0'
    }
}
1
2
3

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

impl Solution {
    pub fn min_partitions(n: String) -> i32 {
        n.chars().map(|c| c.to_digit(10).unwrap()).max().unwrap() as i32
    }
}
1
2
3
4
5
6
7
8
9

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.