Partitioning Into Minimum Number Of Deci-Binary Numbers
Problem
A number is deci-binary if every one of its digits is 0 or 1 (with no leading zeros), e.g. 101 and 1100. Given a string n representing a positive decimal integer, return the minimum number of positive deci-binary numbers that sum to n.
n = "32"3n = "82734"8def min_partitions(n):
best = 0
for ch in n:
d = ord(ch) - ord('0')
if d > best:
best = d
if best == 9:
break
return bestfunction minPartitions(n) {
let best = 0;
for (let i = 0; i < n.length; i++) {
const d = n.charCodeAt(i) - 48;
if (d > best) best = d;
if (best === 9) break;
}
return best;
}int minPartitions(String n) {
int best = 0;
for (int i = 0; i < n.length(); i++) {
int d = n.charAt(i) - '0';
if (d > best) best = d;
if (best == 9) break;
}
return best;
}int minPartitions(string n) {
int best = 0;
for (char ch : n) {
int d = ch - '0';
if (d > best) best = d;
if (best == 9) break;
}
return best;
}Explanation
This looks like a hard partitioning problem, but a single observation collapses it: the answer is just the largest digit in the string.
Think column by column. When you add several deci-binary numbers, each one contributes either 0 or 1 to any given digit column (there is never a carry, because a column can hold at most "number of addends" ones, and we never exceed 9). So if a column of n shows the digit d, you need at least d of the deci-binary numbers to have a 1 in that column. That makes the maximum digit a hard lower bound.
The bound is also achievable. Take k = the maximum digit. Build k deci-binary numbers where, in each column with digit d, exactly d of the k numbers carry a 1. Summing them reproduces every column of n with no carries, so k numbers always suffice.
The algorithm is therefore a one-pass scan: keep a running best and update it with each digit. We can stop early the moment we see a 9, since no digit can beat it.
Example: n = "32". The digits are 3 and 2, so best = 3, and indeed 10 + 11 + 11 = 32 uses exactly 3 deci-binary numbers.