Given 1<= n <= 10^6. At every stage one can apply any one of three operations : (1.) if i%3==0 then i=i/3; (2.) if i%2==0 then i=i/2; (3.) if i>=1 then i=i-1; --------->The target is to apply the above steps till we reach 1 ; We can find minimum number of steps to reach 1 easily by simple dp state !! --------->But what if we need to check whether this can be done in exactly k steps where 0<=k<=n-1. ---------->For Example : 1.{ n=10; if(k==4) ans= yes.(10->9->3->1) if(k==3) ans= no. } Solution Needed !!

Are you sure it is solvable? I mean I almost feel the solution, it doesn't seem unsolvable, but have you come up with it or just read it somewhere?

I am not sure that it is solvable with dp; I saw similar problem on some OJ.

Ok, so I checked my solution again this works for the case when you use all the -1 operations at once and then the *2 and *3 so, this doesn't give the correct answer for the given question.

Your solution is wrong, test from blog

`10 4`

.Sorry earlier I was taking n-> 0 in k steps 10->9->3->1 is actually 3 steps Now taking it to n->1 in k-1 steps.

First let us make brute-force solution: dp[i][j] indicates if it is possible to transform i into 1 in j steps. It can be done in

O(n ^ 2)or inO(n^2 / 64)using bitset. I observed that all cells with 1 in dp[i] are making segment [min_for(i), i — 1]. I checked it for first about 70000 numbers and didn't find mismatch.I guess this can be proved strictly, but i thought something like this: Suppose that for all x < i possible j are making segment [min_for(x), x — 1]. If i isn't divisible by 2 or 3 it is obvius it'll have segment [min_for(i — 1) + 1, i — 1] If i is divisible by 2 and isn't divisible by 3 segment will be union of [min_for(i / 2) + 1, i / 2] and [min_for(i — 1) + 1, i — 1]. It is noticeable that min_for(x) is much less than x (for big x), something related to log(x). And because of this min_for(i) <= i / 2 — 1 and union will make range [min_for(i / 2) + 1, i — 1]. Similarly with other cases. So your task is just to calculate min_for array (it can be done in

O(n)) and if min_for[x] <= k < x answer is YES.