Difficulty while constructing the solution in DP

Please Help me guys with this question.

This question is simple! Just need observation!

First remember that you can use only 1 and 0;

Now Suppose You wanna Make 487 so at minimum you need-

  • Exactly 8 ones(1’s) for digit 8.
  • Exactly 7 ones for digit 7
  • Exactly 4 ones for digit 4.

Now implement this in decreasing order of all 1’s i.e.,
111 111 111 111 011 011 011 010

(Leading zeroes is used for understanding). AS you can see that each position of representation is describing the number of times 1’s occur at respective position in (4,8,7);

Pseudo Code

count=0,div=1,ans[]={0}

for(i, 1 to 6) // 1e6 is the maximum number

{
    x=(n/div)%10;
    
	for(j, 1 to x)
	ans[j]+=div;
    
	count=max(count,x);
    
	div*=10;
} 

Now print count will contain minimum number you need and array contains all numbers in decreasing order.

Hit like if you get your answer otherwise ask again!
6 Likes

This is quite a simple problem and the solution as provided by @bansal1232 is correct, however that is not the dp solution. Keep in mind that dynamic programming is NOT required here and would actually be more time consuming. However you have specifically asked for the dp solution, so here goes.

The first step is to generate and store all quasibinary numbers which will be required by us, that is all quasibinary numbers \le10^6. This is quite simple using a recursive function, and there are only 65 such numbers including 0. Let qb[i] represent the i^{th} quasibinary number available to us.

Next, we should realize that this is the coin change problem, and proceed accordingly. Take a look here. In this problem the quasibinary numbers are equivalent to the coins denominations available. We are going to use the most optimized version, with \mathcal{O}(mn) time complexity and requiring \mathcal{O}(n) space. Of course we must modify the code to find the minimum number of coins required instead of the total number of ways possible to make a certain sum. The logic goes like this, and read this carefully… if for a particular sum j we have a certain way of making it from quasibinary numbers, and we find a quasibinary number qb[i] such that j can be made from qb[i] and a smaller sum (j-qb[i]) using lesser numbers than our current way, we should switch to this way instead. Let dp[i] store the minimum number of quasibinary numbers required to make the sum i, then our our code will be

for(each qbi in qb){
    for(int j=qbi; j<=n; j++){
        if(dp[j] > dp[j-qbi] + 1)
            dp[j] = dp[j-qbi] + 1;
    }
}

This will correctly calculate the minimum number of quasibinary numbers, however for this problem we are also required to display the constituent numbers for n.

To do that we must keep track of which quasibinary number qb[i] we are using to make up each particular sum j. Let usedqb[j] store the last qb[i] value used to improve the value of dp[j]. Now we can break j into usedqb[j] and (j-usedqb[j]). We get one quasibinary value usedqb[j] from this operation. Now we can further break (j-usedqb[j]) into a quasibinary value and another sum… and repeat until the remaining sum becomes 0. We can collect all the quasibinary numbers this way, and print them to get AC verdict.

Complexity is \mathcal{O}(64*n) = \mathcal{O}(n)
Complete solution here.

Feel free to ask if something is not clear. Hope this helps :slight_smile:

5 Likes

I understand what you are trying to do, but don’t understand the reasoning behind it. Please explain your algo and why it works?

Thanks that was really helpfull. Could you explain why @bansal1232 did what he did?

As @bansal1232 explained, a bit of observation shows us that to make 324, we need three 1’s in the hundreds place, two 1’s in the tens place, and four 1’s in the ones place. To get three hundreds we can do 100+100+100. We can also make 300 using thirty 10s, but we will not do that because we want to minimize the number of values we use.
So we need 100+100+100 for 300, 10+10 for 20, and 1+1+1+1 for 4, if we add them we get 324. Now if we can add some of these numbers together we should do that because that would decrease the total count. So the best way to get 324 would be 111+111+101+001.

For another number, suppose 413, the numbers we would use are

 111
 101
 101
 100
=413

I hope the pattern is clear to you now?

Sorry for late replying! But i think @meooow has already provided you the best explanation! As he said i just used a simple looping without any DP.

As it seems to be easy to me where we just need simple mathematics and nothing else!