Very Simple Java Solution With Detail Explanation


  • 11
    K

    To get the DP solution, analyse the pattern first by generating first few solutions
    1: 0
    2: 2
    3: 3
    4: 4
    5: 5
    6: 5
    7: 7
    8: 6
    9: 6
    10: 7
    11: 11
    12: 7
    13: 13
    14: 9
    15: 8

    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

    public int minSteps(int n) {
        int res = 0;
        for(int i=2;i<=n;i++){
            while(n%i == 0){
                res+= i;
                n=n/i;
            }
        }
        return res;
    }

  • 2
    T

    @keshavk The solution is very awesome,however in description for n=1 u wrote that the result is 1,but actually result for n=1 must be 0,we need no operation if n=1
    1: 0
    2: 2
    3: 3
    4: 4
    5: 5
    6: 5
    7: 7
    8: 6
    9: 6
    10: 7
    11: 11
    12: 7
    13: 13
    14: 14
    15: 8


  • 2
    X

    @keshavk Brilliant explanation!
    However, there's a typo:
    If n = 14, the answer should be 9 instead of 14.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.