To get the DP solution, analyse the pattern first by generating first few solutions

Number of A's | Steps |
---|

1 | 0 |
---|

2 | 2 |
---|

3 | 3 |
---|

4 | 4 |
---|

5 | 5 |
---|

6 | 5 |
---|

7 | 7 |
---|

8 | 6 |
---|

9 | 6 |
---|

Now, check the solution.

Eg: n=6

To get 6, we need to copy 3 'A's two time. (2)

To get 3 'A's, copy the 1 'A' three times. (3)

So the answer for 6 is 5

Now, take n=9.

We need the lowest number just before 9 such that (9% number =0). So the lowest number is 3.

So 9%3=0. We need to copy 3 'A's three times to get 9. (3)

For getting 3 'A's, we need to copy 1 'A' three times. (3)

So the answer is 6

Finally to analyse the below code, take n=81.

To get 81 we check

if (81 % 2 ==0) No

if (81 % 3 ==0) Yes

So we need to copy 81/3 = 27 'A's three times (3)

Now to get 27 'A's, we need to copy 27/3= 9 'A's three times (3)

To get 9 'A's, we need to copy 9/3=3 'A's three times (3)

And to get 3 'A's, we need to copy 3/3=1 'A's three times (3)

Final answer is 3+3+3+3 = 12

Last Example, n=18

18/2 = 9 Copy 9 'A's 2 times (2)

9/3=3 Copy 3 'A's 3 times (3)

3/3=1 Copy 1'A's 3 times (3)

Answer: 2+3+3= 8

class Solution: def minSteps(self, n: int) -> int: ans = 0 for i in range(2, n + 1): while n % i == 0: ans += i n /= i return ans |
---|

eg : ans = Solution()

ans.minSteps(889)

**Output-**

**134**