# Partitioning Into Minimum Number Of Deci-Binary Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers)
Canonical: https://scaleengineer.com/dsa/problems/partitioning-into-minimum-number-of-deci-binary-numbers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## 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`_._

**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
## Iterative Subtraction Simulation
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.
**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.
**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`.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Find Maximum Digit
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`.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minPartitions(String n) {
        int maxDigit = 0;
        for (int i = 0; i < n.length(); i++) {
            int digit = n.charAt(i) - '0';
            if (digit > maxDigit) {
                maxDigit = digit;
            }
            // An early exit optimization
            if (maxDigit == 9) {
                return 9;
            }
        }
        return maxDigit;
    }
}
```
### 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`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minPartitions(string n) {
    int ans = 0;
    for (char &c : n)
      ans = max(ans, c - '0');
    return ans;
  }
};

```

### Python

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

```