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

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