Partitioning Into Minimum Number Of Deci-Binary Numbers (Leetcode 1689)

Difficulty: Medium Link: Day 26, May Leetcode Challenge

Problem 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.

Examples

Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32
Input: n = "82734"
Output: 8
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.

Solution

The problem seems very tricky but is very simple we just need a little insight and out of the box thinking. It is recommended to try a few examples yourself to build your intuition. Since we are only allowed to use 0 or 1 (Deci-binary) therefore, any digit in the number would be accumulated by 1s at that place. For a given number, what is the maximum number of times, we will have to add the deci-binaries? Look at the figure.

All other empty places can be replaced with zero. Hence, the answer depends on the maximum value of the digit in the number and our problem simply decomposes to finding the largest digit which is pretty straight forward.

Swift

class Solution {
func minPartitions(_ n: String) -> Int {
var maxCharacter = 0
for c in n {
maxCharacter = max(maxCharacter,Int(String(c),radix:10)!)
}
return maxCharacter
}
}

Python

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

Java

class Solution {
public int minPartitions(String n) {
int maximum = 0;
for (char c : n.toCharArray()) {
maximum = Math.max(maximum, c '0');
}
return maximum;
}
}

Complexity Analysis

Time Complexity: O(M), Where M is the length of string since we need to iterate over string n to find out the maximum digit.

Space Complexity: O(1), since no extra data structure is required. 

Leave a Reply

Your email address will not be published. Required fields are marked *