Skip to main content
Talentd

Partitioning Into Minimum Number Of Deci-Binary Numbers - Solution & Explanation

MediumStringGreedy13 min readAsked at: Amazon, Google, Zoho +1
Practice this problem

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.

 

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.

Approach Overview

Problem Overview: You are given a numeric string n. The task is to split it into the minimum number of deci-binary numbers (numbers containing only digits 0 or 1) such that their sum equals n. The result depends on how many 1s are required in each digit position across all constructed numbers.

Approach 1: Maximum Digit Evaluation (Greedy, O(n) time, O(1) space)

The key observation: every deci-binary number contributes at most 1 to each digit position. If a digit in n is d, you need at least d deci-binary numbers to sum to that position. Therefore, the minimum number of required deci-binary numbers equals the maximum digit present in the string. The algorithm simply iterates through the characters of the string, converts each digit, and tracks the maximum value seen. This greedy observation removes the need to explicitly construct the deci-binary numbers. The scan takes O(n) time and only a few variables, giving O(1) space.

This works because each resulting deci-binary number can contribute a 1 in positions where the original digit still needs value. Once you know the largest digit, you know how many parallel deci-binary layers are required to build the number.

Approach 2: Direct Conversion and Maximum (O(n) time, O(n) space)

This version first converts the numeric string into a list or array of integers, then scans the collection to find the maximum digit. Conceptually it follows the same greedy insight as the previous approach, but separates the parsing and evaluation steps. First iterate through the string and store each digit in an integer array. Then perform a second pass to compute the maximum element.

The algorithmic idea is identical: the maximum digit determines the minimum number of deci-binary numbers needed. However, this approach uses additional memory for the converted array, resulting in O(n) extra space. It can be useful in situations where the digits are reused for additional processing.

Both approaches rely on a simple greedy insight about digit contribution rather than constructing the numbers explicitly. Problems like this commonly appear in greedy and string processing categories, where scanning input once reveals the optimal answer.

Recommended for interviews: The Maximum Digit Evaluation approach. Interviewers expect you to recognize the greedy property quickly: the largest digit determines the number of required deci-binary layers. A brute-force construction approach would be unnecessarily complex, while identifying the max digit shows strong problem reduction and reasoning skills.

Approach 1: Approach 1: Maximum Digit Evaluation

The key to solving this problem is understanding the relationship between the digits of the number and the deci-binary numbers. The minimum number of deci-binary numbers needed is dictated by the maximum digit in the string representation of the number. This is because to construct the number using deci-binary numbers (which only contain 0 and 1), at least one of these numbers must have a '1' in each digit position where the given number is non-zero. Each deci-binary number can only add 1 to each digit position.

In this C implementation, we iterate through the string of the number, keeping track of the maximum digit found. Since deci-binary numbers can only increment each position by 1, the maximum digit will determine the minimum number of such numbers required.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Approach 2: Direct Conversion and Maximum

Instead of iterating through the string directly, an alternate way to solve the problem can be to map the string into an array of numbers first, then find the maximum in that array. However, this adds overhead without practical advantage, since the core of the solution relies on identifying the maximum digit in the string.

While this approach doesn't effectively differ in the outcome or complexity, it demonstrates the same maximum digit principle, emphasizing direct character handling in the number string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), n being the length of the string.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Quick Thinking

The problem is equivalent to finding the maximum number in the string.

The time complexity is O(n), where n is the length of the string. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Maximum Digit Evaluation

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we only use a constant amount of extra space.

Approach 2: Direct Conversion and Maximum

Time Complexity: O(n), n being the length of the string.
Space Complexity: O(1).

Quick Thinking—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Maximum Digit Evaluation (Greedy)O(n)O(1)Best general solution. Single pass over the string with constant space.
Direct Conversion and MaximumO(n)O(n)Useful if digits must be reused later or stored for additional processing.

Video Solution

Partitioning Into Minimum Number Of Deci-Binary Numbers | Brute Force | Trick | Leetcode 1689 | MIK • codestorywithMIK • 6,349 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Partitioning Into Minimum Number Of Deci-Binary Numbers easy or hard?
The problem is rated Medium on LeetCode but is considered relatively straightforward once the greedy insight is discovered. Many candidates initially try constructing deci-binary numbers, but recognizing that the maximum digit determines the answer simplifies the solution to a single pass.
Partitioning Into Minimum Number Of Deci-Binary Numbers Python/Java solution
The implementation is straightforward in Python, Java, C++, or JavaScript. Iterate through each character of the string, convert it to a digit, and update the maximum value seen so far. Return that maximum digit as the answer. The runtime remains O(n) across all languages.
How to solve Partitioning Into Minimum Number Of Deci-Binary Numbers in O(n)?
Iterate through the string and compute the maximum digit encountered. Each deci-binary number contributes at most one to a digit position, so the largest digit determines how many numbers are required. This single scan approach solves the problem in linear O(n) time and constant space.
What is the best approach for Partitioning Into Minimum Number Of Deci-Binary Numbers?
The optimal approach is a greedy scan that finds the maximum digit in the string. Since each deci-binary number can contribute at most 1 to a digit position, a digit value d requires at least d numbers. Therefore the minimum count equals the largest digit in the string. This solution runs in O(n) time with O(1) space.
Is Partitioning Into Minimum Number Of Deci-Binary Numbers asked at Google/Amazon/Meta?
This problem reflects the type of greedy reasoning frequently asked in interviews at companies like Google, Amazon, and Meta. While the exact problem may not always appear, the concept of reducing a problem to a key invariant or maximum constraint is common in coding interviews.
What data structure is used in Partitioning Into Minimum Number Of Deci-Binary Numbers?
The problem mainly uses simple string traversal and integer comparison. No advanced data structures are required. Some implementations convert the string into an integer array, but the optimal solution only tracks the maximum digit during iteration.
What is the time complexity of Partitioning Into Minimum Number Of Deci-Binary Numbers?
The optimal algorithm runs in O(n) time where n is the length of the numeric string. You only need a single pass through the digits to track the maximum digit. Space complexity is O(1) because only a few variables are used.

Ready to solve this problem?

Practice Partitioning Into Minimum Number Of Deci-Binary Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring