Problem statement

https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/

Solution

We asked the question: what is minimum number of deci-binary numbers we can have, so it is example + estimate problem. It means that for strict proof you should have two parts:

  1. Estimation: say, that for number n, minimum number of parts is some number f(n), that is it is impossible to make it with lesser number of parts.
  2. Example: provide example, where we have exaclty f(n) parts.

If it was math olympiad, and you skip one of the parts, usually you will get only half of the points (it really depends of these two parts, one of the parts can be very easy and another difficult, but you for sure will lose some points). We are in programming olympiad setup, so we do not need to have strict proof here, but if it is interview you still need. So, what is our guess. We have 0 and 1 only, so let us try to proof that answer is maximum digit in our number.

  1. Estimation. Let us for simplicity consider number 9182436, so we need to prove that it is impossible to partition it into 8 parts. Indeed, if we sum numbers with digits only 0 or 1, then we can have digits <=8, so there is no way we can get our number. Similarly it will work for all other numbers.
  2. Example. Let us consider again number 9182436. Now, we need to give example, how it can be partitioned into 9 numbers, or prove that this example exists. Here the process is the following. Let us look at all digits, which are not-zero, and subtract 1 from all of them: we have 9182436 = 8071325 + 1111111, then repeat this process: = 7060214 + 1011111 + 1111111 and so on. How many times we need to repeat this process? Exactly 9 in fact, because each time biggest digit is reduced by 1. Here we considered number 9182436 for more intutions, exaclty the same idea will work on all numbers.

So, we proved, that maximum digit is the correct answer. Note, that estimation and example have quite similar structure, but nevertheless you still need to provide both of them to have a strict proof. It is similar to when you need to prove that one statement is equivalent to another, you need to prove it in both sides. I think this is the reason why problem is marked medium, not easy.

Complexity

Time is just O(n) to find the biggest digit and space is O(1).

Code

class Solution:
    def minPartitions(self, n):
        return max(int(i) for i in n)