1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

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.

Example 1:
Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32

Example 2:
Input: n = "82734"
Output: 8

Example 3:
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.

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


Video coming soon!



Subscribe for more updates


Algorithm/Insights

The problem can be solved by finding the maximum digit present in the given decimal number. Consider these examples:

    1. If the input has only one digit, then you need to add as many ones as the value of this digit to get a sum equal to the input. For example, if the input is "7", you need to add seven ones together to get a sum of 7: "1+1+1+1+1+1+1=7".

    2. If the input has multiple digits, you can solve for each digit independently. For example, if the input is "32", you can solve for the digit "3" and "2" independently, and then merge the answers to form numbers that add up to the input.

    3. To solve for each digit, you need to find the maximum digit in the input. Then, you can add as many ones as the value of that digit to get a sum equal to the input. For example, if the input is "32", the maximum digit is "3". So, you need to add three ones together to get a sum of 3: "1+1+1=3". Then, you can solve for the digit "2" in the same way: "1+1=2". Finally, you can merge the answers to form the numbers that add up to the input: "11+11+10=32".


Code Snippet

			
package com.ideserve.sakshi.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Partitioning Into Minimum Number Of Deci-Binary Numbers
 *
 * @author Sakshi
 */
class Solution {
    public int minPartitions(String n) {
        char max = 0;
        for (int i = 0; i < n.length(); i++) {
            char ch = n.charAt(i);
            if (max < ch) {
                max = ch;
            }
        }
        return (int)(max - '0');
    }
}
		

Order of the Algorithm

Time Complexity is O(n), where n is the number of digits in the decimal number. This is because we are traversing each digit only once.
Space Complexity is O(1), as we are not using any extra space other than the variables needed to store the input and output values.


Contribution

  • Sincere thanks from IDeserve community to Sakshi Kataria for compiling current post.


    Sakshi Kataria