1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Problem

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.

Problem Summary

If a decimal number has no leading zeros and each digit is either 0 or 1, then the number is a deci-binary number. For example, 101 and 1100 are deci-binary numbers, while 112 and 3001 are not. Given a string n representing a decimal integer, return the minimum number of deci-binary numbers whose sum is n.

Solution Approach

• This problem can also be considered easy; once you understand it, the code is just 3 lines.
• To form n using decimal numbers composed of 0s and 1s, you only need to place 0s and 1s in each digit position of n one by one. For example, n = 23423723, which is an 8-digit number. The largest digit is 7, so at least 7 numbers are needed to sum up to this n. The hundreds digit of these 7 numbers is all 1, and the other digit positions can be 0 or 1 as needed. For example, if the ten-thousands digit is 2, then among these 7 numbers, choose any 2 numbers whose ten-thousands digit is 1, and let the ten-thousands digit of the other 5 numbers be 0.

Code

package leetcode

func minPartitions(n string) int {
	res := 0
	for i := 0; i < len(n); i++ {
		if int(n[i]-'0') > res {
			res = int(n[i] - '0')
		}
	}
	return res
}