Description
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 <= 105nconsists of only digits.ndoes not contain any leading zeros and represents a positive integer.
Solutions
This solution takes a top-down search approach, starting from the largest digit (9) and working downward. For each digit from 9 to 2, it uses match() with a regex pattern to check if that digit exists anywhere in the string; the first match found is returned. If no digit from 2 to 9 is found, it returns 1 as the minimum possible answer. While conceptually clear, this approach may be less efficient than scanning left-to-right since it performs multiple passes for large digits.
/**
* @param {string} n
* @return {number}
*/
var minPartitions = function(n) {
for (let i = 9; i >= 2; i--) {
if (n.match(RegExp(i))) {
return i;
}
}
return 1;
};