Java most concise solution (No DP, No recursion, one loop, 10 ms)


  • 0
    J

    The main thought is: nomatter how many A u already have,
    if u want to double it, u need 2 more steps. (copy, paste)
    if u want to triple it, u need 3 more steps. (copy, paste paste)
    if u want to 4 times it, u need 4 more steps (copy paste, paste paste)
    Then the solution is: check if n can divide by k (k from 2 - n), if yes, it means it need k steps to build the string from n/k to n.
    Then the code is very concise below:

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

Log in to reply
 

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