Problem Statement in English

You’re given a string n representing a positive decimal integer. You need to find the minimum number of positive deci-binary numbers needed so that they sum up to n.

A deci-binary number is a decimal number that consists of only 0s and 1s and has no leading zeros. For example, 101 and 1100 are deci-binary numbers, while 112 and 3001 are not.

Approach

As the hint provided by LeetCode suggests, the answer is the maximum digit in the string n. This is because we can create a deci-binary number for each digit in n and sum them up to get n. For example, if n is 123, we can create the following deci-binary numbers:

  • 111
  • 011
  • 001

And we’re done!

Solution in Python


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

Complexity

  • Time: $O(n)$
    Where $n$ is the length of the string n. Since we need to iterate through the string once.

  • Space: $O(1)$
    Since we are using only a constant amount of space.

Mistakes I Made

I had to look up the hint provided by LeetCode :(

And we are done.