LeetCode 1689 — Partitioning Into Minimum Number of Deci-Binary Numbers (C++) (Day-01)

When I first saw this problem, it looked like a math + greedy problem, but the solution turns out to be surprisingly simple.

Let’s break it down.

---

📌 Problem

A deci-binary number is a number where each digit is either 0 or 1.

Examples:

101
1100
10001

Invalid examples:

112
3021

You are given a decimal string n.

Your task is to return the minimum number of deci-binary numbers needed so their sum equals n.

---

💡 Key Observation

Each deci-binary number can contribute at most 1 to any digit position.

Example:

n = "32"

We can build it like this:

10
11
11

Sum:

10 + 11 + 11 = 32

We needed 3 numbers.

Why?

Because the largest digit in 32 is 3.

---

🔑 Core Insight

The minimum number of deci-binary numbers required = the maximum digit in the string.

Why this works:

If a digit in n is 8, we need at least 8 numbers, since each deci-binary number can contribute only 1 at that position.

Example:

n = "82734"

Digits:

8 2 7 3 4

Maximum digit:

8

So the answer is:

8

---

🧠 Algorithm

1. Traverse the string.
2. Convert each character to an integer.
3. Track the maximum digit.
4. Return that value.

---

💻 C++ Implementation

class Solution {
public:
    int minPartitions(string n) {
        int maxi = 0;

        for(char c : n) {
            maxi = max(maxi, c - '0');
        }

        return maxi;
    }
};

---

⏱ Complexity Analysis

Time Complexity

O(n)

We scan the string once.

Space Complexity

O(1)

Only one variable is used.

---

🎯 Interview Insight

This problem tests your ability to spot constraints in digit-based problems.

Instead of constructing numbers, think about:

What is the minimum contribution needed per digit position?

Since each deci-binary number contributes at most 1, the largest digit determines the answer.

---

✨ Final Thought

Sometimes the hardest part of a problem is not overthinking it.

The entire solution boils down to:

Find the maximum digit.

And that’s it.