1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

I feel your tears. 😭😭 😭

Introduction

We all need a little help now and again. Sometimes simple problems can be the hardest ones to solve. Maybe it’s problem-solving fatigue, lack of sleep, or just plain living life. Let’s dive into this “simple” problem together and tackle what makes it so hard to grasp. You won’t need to know a lot about math or computer science. Just bring your desire to learn and grow.

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.

Hashing it out

Let’s start with understanding what we are given. The description for “deci-binary” is pretty straightforward. Let’s write those out with a solid bulleted list. I find this method helps me understand what information I am given.

• Deci-Binary looks like this.. 101,1100, or 101010.
• No leading zeros/ doesn’t start with a zero in Deci-Binary.
• Not like this… 112 or 3001
• No numbers other than 0 or 1

Now the rest of the prompt is asking for “…the minimum number of positive deci-binary numbers needed so that they sum up to n.”

• n is the number we are given as a string
• n should be made up of these deci-binary numbers
• They look like this 101, 1100, etc…
• We want to return the least amount of these numbers!

Which is also pretty straight-forward. Yet something doesn’t add up when we look at the examples. The first example doesn’t divide the input of 32 evenly, yet we get a sum of the input number. Normally with this sort of problem, there is a nuanced pattern.

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

Let’s take a closer look at these examples. From what we have read so far, it doesn’t seem like we aren’t given everything we need to solve this writing problem. Maybe there is some secret pattern here.

Example 1:

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

Notice the three 3s in the first example. That seems interesting, but what about the other ones?

Example 2:

Input: n = "82734"
Output: 8

Example 3:

Input: n = "27346209830709182346"
Output: 9

Definitely, a pattern going on here. It looks like the biggest number in the string needs to be returned. Probably as a string. So how can we do this?

• Break strings into individual pieces and put them in an array.
• duplicates of the largest number do not seem to matter
• Sort those numbers, from big to small (descending order)
• return the first one (first index)

We can easily do this with .split() and .sort() methods. Then will pull off the first position in the array and return it. Wow, I didn’t even need to know anything deeply technical here. See below for the formal solution.

Solution

const minPartitions = function(n) {
    
    return n.split("").sort((a, b) => b - a)[0];
    
}

How does this work?

Let’s look at each number in a given string. How about 32 from example 1. What’s the largest value? What does that look like in deci-binary?

Example 1:

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

• 3 is made of 111, which is the largest number in the string
• 2 is made of 110, which is the next largest number in the string
• We return the largest number, that’s 3.
• No number can be greater than 3 cause it’s the largest.
• Every other number has the same length as the largest.
• The difference between each number is made up of zeroes.

Another way to say this find the biggest number in a positive integer. That number will give you the fewest amount of deci-binary numbers it takes to total up to that given number. Pretty interesting pattern, right?

Conclusion

See how we didn’t really need knowledge about math or computer science to solve this problem. It was pretty straightforward in writing, yet it seems to leave you with just enough to figure out the solution. All we did was find a pattern in the examples of the problem. Once we found it, everything clicked into place. We even dug a little deeper into understanding why this pattern appears in the first place.

Links Below

LeetCode: https://leetcode.com/

String Method Split: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/split

Array Method Sort: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort