Probable Solution of Helping Hand Question


This Question can be solved using something like divide and conquer,
so if we want answer for n,first we will count the number of greatest power of primes below n, lets call count of them as y,
means, if n=7 than primes are 2,3,5,7,
and greatest power of those are 4,3,5,7,
so,first we will make these four number equal by lcm ,let it take x steps
than answer will be x+(n-y),as for (n-y) number it is going to take 1 step for each.
now,we want the x,
if we have y=4:-
eg:- 4,3,5,7
taking two step 12,12,35,35
again take two step 420 420 420 420
so for x=4 here as we took 4 steps.
so answer for 7 is 4+(7-4) that is 7, and the answer by this code is lesser than n+p-3 for many numbers.
so for finding x:
this can be used:-
cnt_dp[2] will be 1 and cnt_dp[1]=0;


seems right

It seems right to me.

1 Like

the above code gives output 10 for n=10 while 9 for n=11 shouldnt number of operations increase with n

bro,i corrected it now!

1 Like

something is still wrong bro, for n=23 the output is 30 , but i have done by hand i got 27 for 23;
even n+p-3 method gives answer 29 it can surely be don in in 27 though

ohh,i see, this solution is incorrect,my bad,sorry for bothering.

1 Like

Can it be done in 26?? I tweaked a few things in my solution and it gives answer as 26 for 23. I can’t verify it though

I did the same in contest it was wrong answer bro

I am not sure. i could not find a solution with 26, the smallest i could go for n=23 was 27