1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Problem

Tags: String, Greedy

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 <= 10^5
• n consists of only digits.
• n does not contain any leading zeros and represents a positive integer.

Code

GO

// 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers (6/19/53372)
// Runtime: 0 ms (94.81%) Memory: 6.49 MB (58.44%) 

func minPartitions(n string) int {
    result := '0'
    for _, c := range n {
        if c > result {
            result = c
        }
    }
    return int(result - '0')
}

JS

// 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers (6/12/53372)
// Runtime: 84 ms (86.50%) Memory: 43.05 MB (94.89%) 

/**
 * @param {string} n
 * @return {number}
 */


var minPartitions = function (n) {
    // 這題就是找字串中最大的數就好，代表同位置最多需幾個 1
    
    // 1. 最簡單的方法
    // return Math.max(...n.split(""));
    
    // 2. 高速的方法
    for (var i = 9; i > 1; i--) 
        if (n.includes(i)) return i;
    return 1;
    
    /* 3. 節省記憶體的方法
    let max = 1;
    for (let num of n) {
        if (num > max) max = num;
        if (max == 9) break;
    }
    return max;
    */
};