Skip to content

1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

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

Solutions

Solution 1: Quick Thinking

The problem is equivalent to finding the maximum number in the string.

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

1
2
3
class Solution:
    def minPartitions(self, n: str) -> int:
        return int(max(n))

1
2
3
4
5
6
7
8
9
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minPartitions(string n) {
        int ans = 0;
        for (char& c : n) {
            ans = max(ans, c - '0');
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minPartitions(n string) (ans int) {
    for _, c := range n {
        if t := int(c - '0'); ans < t {
            ans = t
        }
    }
    return
}

1
2
3
function minPartitions(n: string): number {
    return Math.max(...n.split('').map(d => parseInt(d)));
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn min_partitions(n: String) -> i32 {
        let mut ans = 0;
        for c in n.as_bytes() {
            ans = ans.max((c - b'0') as i32);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int minPartitions(char* n) {
    int ans = 0;
    for (int i = 0; n[i]; i++) {
        int v = n[i] - '0';
        if (v > ans) {
            ans = v;
        }
    }
    return ans;
}

Comments