Java math solution


  • 2

    I think for this problem we just need to find all the prime factors for the number, then add them up.

    public int minSteps(int n) {
            if(n == 1) return 0;
            if(n <= 5) return n;
            int count = 0;
            int a = 2;
            while(a * a <= n) {
                while(n % a == 0) {
                    count += a;
                    n /= a;
                }
                a++;
            }
            if(n > 1) count+= n;
            return count;
        }
    

  • 0
    T

    Can you explain a little more about your algorithm?


  • 0
    J

    @Kamishirasawa-Keine said in Java math solution:

    public int minSteps(int n) {
    if(n == 1) return 0;
    if(n <= 5) return n;
    int count = 0;
    int a = 2;
    while(a * a <= n) {
    while(n % a == 0) {
    count += a;
    n /= a;
    }
    a++;
    }
    if(n > 1) count+= n;
    return count;
    }

    Explanation :
    To multiply the string by k times, the most naive way is to copy once and paste k-1 times. That takes k steps.

    Notice how this becomes a multiplication problem : the operation can be treated as multiplying the existing string k times, and it takes k steps.

    Going back to k. We don't need to take k steps to multiply the string k times, if k is not a prime number. Only when k is a prime number, we need to take at least k steps to achieve k multiplication, because there's no other way around to further divide the operation., otherwise, let's say k's not a prime number and its prime factors are x,x,y,y,z, i.e, k = x * x * y * y * z. Remember multiplication of x times means x steps (because x is a prime number). so to achieve k, we actually only need x+x+y+y+z steps.

    QED.


Log in to reply
 

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