Partitioning Into Minimum Number Of Deci-Binary Numbers
Partitioning Into Minimum Number Of Deci-Binary Numbers is a medium arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (largest digit), runs in O(L) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (peel off one deci-binary number at a time) up.
Problem
Call a decimal number deci-binary if every one of its digits is 0 or 1 and it has no leading zeros, for example 101 or 1100, but not 112 or 3.
You are given a positive decimal integer as a string n. Return the minimum number of positive deci-binary numbers whose sum is exactly n.
Examples
Example 1
- Input
n = "413"- Output
4- Why
- 111 + 101 + 101 + 100 = 413. The leading 4 needs four numbers, each contributing one 1 in that column.
Example 2
- Input
n = "1001"- Output
1- Why
- 1001 is already deci-binary.
Example 3
- Input
n = "5097"- Output
9- Why
- The digit 9 forces at least nine numbers, and nine are enough.
Constraints
1 <= n.length <= 10^5nconsists of digits only and has no leading zeros.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (peel off one deci-binary number at a time) | O(9 · L) | O(L) |
| Optimal (largest digit) | O(L) | O(1) |
1Brute force (peel off one deci-binary number at a time)
O(9 · L)At most 9 rounds, each touching all L digits.O(L)A mutable copy of the digits.Repeatedly subtract the deci-binary number that has a 1 wherever the current value has a non-zero digit. Each round decreases every non-zero digit by one and never needs a borrow. Count the rounds until everything is zero.
- digits = the characters of n as ints; rounds = 0.
- While some digit is non-zero: decrement every non-zero digit; rounds++.
- Return rounds.
class Solution {
public int minPartitions(String n) {
int[] digits = new int[n.length()];
for (int i = 0; i < n.length(); i++) digits[i] = n.charAt(i) - '0';
int rounds = 0;
while (true) {
boolean any = false;
for (int i = 0; i < digits.length; i++) {
if (digits[i] > 0) {
digits[i]--;
any = true;
}
}
if (!any) return rounds;
rounds++;
}
}
}class Solution:
def minPartitions(self, n: str) -> int:
digits = [ord(c) - 48 for c in n]
rounds = 0
while True:
any_left = False
for i in range(len(digits)):
if digits[i] > 0:
digits[i] -= 1
any_left = True
if not any_left:
return rounds
rounds += 1class Solution {
public:
int minPartitions(string n) {
vector<int> digits(n.size());
for (size_t i = 0; i < n.size(); i++) digits[i] = n[i] - '0';
int rounds = 0;
while (true) {
bool any = false;
for (int& d : digits) {
if (d > 0) {
d--;
any = true;
}
}
if (!any) return rounds;
rounds++;
}
}
};function minPartitions(n) {
const digits = Array.from(n, (c) => c.charCodeAt(0) - 48);
let rounds = 0;
while (true) {
let any = false;
for (let i = 0; i < digits.length; i++) {
if (digits[i] > 0) {
digits[i]--;
any = true;
}
}
if (!any) return rounds;
rounds++;
}
}2Optimal (largest digit)
O(L)One pass over the string, often less thanks to the early exit at 9.O(1)One integer.A deci-binary number contributes at most 1 to each column, and there are no carries when adding them up digit by digit (a column with k numbers adds to k ≤ 9). So the column holding the largest digit needs at least that many numbers, and the peeling process above shows that many is always enough. The answer is just the maximum digit.
- best = 0; for each character c, best = max(best, c - '0'); stop early at 9.
- Return best.
class Solution {
public int minPartitions(String n) {
int best = 0;
for (int i = 0; i < n.length() && best < 9; i++) {
best = Math.max(best, n.charAt(i) - '0');
}
return best;
}
}class Solution:
def minPartitions(self, n: str) -> int:
best = 0
for c in n:
best = max(best, ord(c) - 48)
if best == 9:
break
return bestclass Solution {
public:
int minPartitions(string n) {
int best = 0;
for (size_t i = 0; i < n.size() && best < 9; i++) {
best = max(best, n[i] - '0');
}
return best;
}
};function minPartitions(n) {
let best = 0;
for (let i = 0; i < n.length && best < 9; i++) {
best = Math.max(best, n.charCodeAt(i) - 48);
}
return best;
}Edge cases to test
- A single digit, e.g. "7": answer 7
- Only 0s and 1s: answer 1
- A 9 anywhere: answer 9 (the maximum possible)
- Very long strings: do not convert to a number
Hints
Hint 1
Each deci-binary number adds at most 1 to every digit position. What does that say about the column with the biggest digit?
Hint 2
Can you always reach the target using exactly that many numbers? Think of peeling off one deci-binary number at a time.
FAQ
What is the best time complexity for Partitioning Into Minimum Number Of Deci-Binary Numbers?
Optimal (largest digit) runs in O(L) time and O(1) extra space. One pass over the string, often less thanks to the early exit at 9.
Which pattern does Partitioning Into Minimum Number Of Deci-Binary Numbers use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Partitioning Into Minimum Number Of Deci-Binary Numbers?
Yes. Brute force (peel off one deci-binary number at a time) takes O(9 · L) time and O(L) space. Repeatedly subtract the deci-binary number that has a 1 wherever the current value has a non-zero digit.
Which edge cases should I test for Partitioning Into Minimum Number Of Deci-Binary Numbers?
A single digit, e.g. "7": answer 7; Only 0s and 1s: answer 1; A 9 anywhere: answer 9 (the maximum possible); Very long strings: do not convert to a number.