Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A deci-binary number contributes at most one to each decimal position. If the largest digit of n is d, at least d summands are required. That bound is achievable: for each layer from one through d, place a one wherever the corresponding digit of n is at least that layer. Their column sums reproduce n without carries.

Approach

Find the largest character in the decimal string and convert it to an integer. Decimal digit characters have the same ordering as their numeric values, so this returns the largest digit directly. The construction argument proves that this simple lower bound is also the minimum number of summands.

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

Complexity analysis

Let d be the number of input digits. Both displayed implementations scan the string once, taking O(d) time and O(1) auxiliary space.