Difficulty: Medium Link: Day 26, May Leetcode Challenge
A decimal number is called deci-binary if each of its digits is either
1 without any leading zeros. For example,
1100 are deci-binary, while
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
Input: n = "32" Output: 3 Explanation: 10 + 11 + 11 = 32
Input: n = "82734" Output: 8
Input: n = "27346209830709182346" Output: 9
1 <= n.length <= 105
nconsists of only digits.
ndoes not contain any leading zeros and represents a positive integer.
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.
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.