https://www.codechef.com/DEM2020/problems/HELPHAND

Can anyone explain how is the output for 7 is 8 when it should have been 7.

@admin

Can you show the 7 steps in which you will achieve this?

Actually the solution is **number_of_primes[n] + n - 3**. Before 7 there are 4 primes(2, 3, 5, 7). We need to find max power of each prime before n and multiple them with each other, then replace other elements.

For 7:

1 2 3 4 5 6 7

1 2 3 4 35 6 35

1 2 105 4 105 6 35

1 2 420 420 105 6 35

420 2 420 420 105 6 35

420 420 420 420 105 6 35

420 420 420 420 420 6 35

420 420 420 420 420 420 35

420 420 420 420 420 420 420

(6,7)=42

(4,5)=20

(4,6)=420

(5,7)=420

(1,7)=420

(2,7)=420

(3,7)=420

Yes Iām also confused because from my side steps are

Optimal steps are: [1,2,3,4,5,6,7]->

[1,2,3,4,5,42,42]->

[1,2,3,20,20,42,42]->

[1,2,3,420,20,420,42]->

[1,2,3,420,420,420,420]->

[420,2,3,420,420,420,420]->

[420,420,3,420,420,210,42]->

[420,420,420,420,420,420,420]

and answer should be 7

yeah, i got the same problem

please explain the solution number of primes+n-3

yes mine is coming 7

1 2 3 4 5 6 7

LCM(4,5)=20;

LCM(6,7)=42;

1 2 3 20 20 42 4 2

LCM(20,42);

LCM(20,42)=420;

1 2 3 420 420 420 420

4 + 3 = 7 operations.

can anybody tell where i am wrong please

I did this but my output is 8. Just that my solution had a TLE verdict

how it is 8 for 7 ony tell this much please

bruh if you are getting tle try to run for 10^6 on your computer copy paste the output in in a array of 10^6 and run the code again to get the output in O(1) time

Actually, the **final LCM** must be **LCM of all numbers**, so it contains **max power of each prime** before N including.

The steps seem to be correct to me ā¦ And now I am wondering how did my solution pass . My code gives 8 for this case. Thanks for putting up a discussion for this.

You need to create array of **number_of_all_primes_before** 1000000 just once to solve TLE issue.

yeah i know that about lcm of all numbers , i just dont get your solution. of using number of primes[n] +n -3

You need to create array of **number_of_all_primes_before** 1000000 just once to solve TLE issue and the answer will be **number_of_all_primes_before[n]** + n - 3 seconds.

@fyter_112

[1, 2, 3, 4, 5, 6, 7] =>

[1, 2, 3, 4, 5, 42, 42] =>

[1, 2, 3, 4, 210, 210, 42] =>

[1, 2, 3, 420, 420, 210, 42] =>

[1, 2, 420, 420, 420, 210, 42] =>

[1, 420, 420, 420, 420, 210, 42] =>

[420, 420, 420, 420, 420, 210, 42] =>

[420, 420, 420, 420, 420, 210, 420] =>

[420, 420, 420, 420, 420, 420, 420]

You are getting 4 as output for 4 while it should had been 3

Oh okay bro thanks