1. [Medium. 1689] - Partitioning Into Minimum Number Of Deci-Binary Numbers

Leetcode 

Problem Statement

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.

Intuition

If you don’t get an intuition, best thing to do is to try out examples, start from the simplest of examples and try to reason with yourself on how the output is derived each time.

Deci-binary numbers goes like this -> 0, 1, 10, 11, 100, 101, 110, 111, 1000 …

Consider single digit n values, for n = 0, minimum number of positive deci-binary numbers needed is 0, for n=1, it is 1 (1), for n = 2, it will be 2 ( 1 + 1 ), n=3 ( 1 + 1 + 1) it will be three. Why is that? Since we are looking for the minimum number of possible deci-binary values that add up to n, we need to consider the maximum deci-binary numbers. So that means for 1 digit numbers the maximum that we can add is 1 digit deci-binary number ( i.e. 1, except for n=0) and based on the value of n, we need to repeat adding 1, n number of times. So to generalize for 1-digit n values, the minimum number of positive deci-binary numbers needed to add up to n will be n.

Now let’s expand on this thought a little bit by considering 2-digit n values. let’s consider n=56. Here maximum deci-binary value that we can first consider is 11. How many times can we add 11 to get something less than 56? it is 5 ( 11 + 11 + 11+ 11+ 11 ). This will give us 55, now to get 56 we just have to add 1 to it, so minimum number of deci-binary values needed here is 6 ( 11+ 11+ 11+ 11+ 11+ 1). Now notice something cool here: to get 56, we can consider the digits separately as below:

50   +   6   =  56
----    ----
10   +   1      11
10   +   1      11
10   +   1      11
10   +   1      11
10   +   1      11
         1 ----> 1

56 is nothing but 50 + 6, to get 50 we would need five 10s and to get 6 we would need six 1s. Clubbing this we will get five 11s and one 1. So in total we need 6. The output is 6. Now, What if n=52. Then a similar breakdown would be as follows:

50   +   2   =  52
----    ----
10   +   1      11
10   +   1      11
10              10
10              10
10 -----------> 10

Here the output is 5. Notice something beautiful - here the highest digit is 5. Notice irrespective of the placement of the highest digit, the highest digit is what that determines the final output and that output is same as the highest digit’s value. For 56, output was 6, for 52 the output was 5.

With this generalization, consider n=95, it will be 9! Infact this will extend to all n values with any number of digits! Let’s say n=471, we can break it down as below:

400   +   70   +  1   = 471
----    ----    ----
100   +   10   +  1     111
100   +   10            110
100   +   10            110
100   +   10            110
          10             10
          10             10
          10 ----------> 10

Here the largest Digit is 7, therefore the output i.e. the minimum number of deci-binary numbers needed to add up to n is 7.

Approach

Since now we know that the output is same as the largest digit in the number, we just have to traverse each digit in the given “string” , convert each character to number (NOTE: IMP - do not use Number() method use implicit - ‘0’ instead as precision might be lost as number grows), check for max digit, assign if greater than current max and finally return the max digit value.

Complexity

TC: O(n) SP: O(1)

Solution

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function(n) {
    let maxDigit = 0;
    for(let char of n){
        const digit = char - '0'; // converts char to number implicitly
        if(digit > maxDigit) {
            maxDigit = digit;
        }
    }
    return maxDigit;
};