---

1. Problem Summary

You are given a string n representing a positive decimal integer.
Your task is to determine the minimum number of positive deci-binary numbers whose sum equals n.

A deci-binary number is defined as:

• A number composed only of digits 0 or 1
• Leading zeros allowed
• Example valid deci-binary numbers: 1, 10, 101, 11001

Goal:

Find the minimum count of deci-binary numbers needed so that
their digit-wise sum equals n.

Example:

Input: n = "32"
Output: 3
Explanation:
  32 = 10 + 11 + 11  (3 deci-binary numbers)

---

2. Key Insights

Insight 1: Digits add independently by position

Since deci-binary numbers only contain 0 or 1 in each digit place, summing them builds the final number column by column.

Insight 2: The limiting factor is the largest digit

To produce digit d in a position, we need at least d deci-binary numbers contributing a 1 in that position.

Example:

Digit 5 requires:

1 + 1 + 1 + 1 + 1

Therefore:

Minimum number of deci-binary numbers needed = max digit in n

Insight 3: No construction required

We do NOT need to:

• Generate deci-binary numbers
• Simulate addition
• Perform dynamic programming

Simply scanning the string is enough.

---

3. Approach

Scan digits and find maximum digit value

Steps:

1. Initialize maxDigit = 0
2. Loop through every character in string n
3. Convert to numeric digit
4. Update maxDigit if larger
5. After loop, return maxDigit

---

4. Time and Space Complexity

Time Complexity:

O(N)

Where N = length of the string

Space Complexity:

O(1)

No extra storage besides variables

---

5. Java Solution

class Solution {
    public int minPartitions(String n) {
        int maxDigit = 0;

        for (char c : n.toCharArray()) {
            int digit = c - '0';
            maxDigit = Math.max(maxDigit, digit);

            if (maxDigit == 9) {
                return 9; // early optimization since 9 is maximum possible
            }
        }

        return maxDigit;
    }
}

---

6. Dry Run Examples

Example 1

Input:

"32"

Digits:
3, 2
max = 3

Output:

3

---

Example 2

Input:

"82734"

Digits:
8,2,7,3,4
max = 8

Output:

8

---

Example 3

Input:

"27346209830709182346"

Largest digit = 9

Output:

9

---

Example 4

Input:

"11111"

All digits are 1
max = 1

Output:

1

---

Example 5

Input:

"0"

Largest digit = 0

Output:

0

---

7. Why This Solution Works

• Each digit contributes independently
• Deci-binary numbers can only add 1 per position
• So number of required numbers equals highest digit needed
• This is mathematically minimal and sufficient

---

8. Common Mistakes

1. Thinking DP is required
2. Trying to construct deci-binary sequences
3. Misinterpreting as binary decomposition
4. Forgetting digits are characters, not integers
5. Ignoring fast early exit when max digit hits 9