Explanations for the solutions


  • 0
    B

    My first post.

    There are many good solutions. Here, I am trying to explain the idea behind them. (In my opinion, it is not very obvious, even you may write the code correctly.)

    If N is a prime number, we have to copy A for N time.

    Consider a composite number N, it can be decomposed as p1 * p2 *...pk.
    Define F(N) as the number of steps. F(N) is F(N/p1) +p1 = F(N/p1p2) + p1 + p2 = F (1) + p1 + p2 + ... pk.

    The problem is how to select these values to minimize F(N) under the constrain: p1 * p2 *...pk = N.

    In high school, we knew p1 + p2 >= sqrt(p1 * p2); it is equal when p1 = p2. And the summation increases when the difference between p1 and p2 increases. The similar rule also applys for p1+p2+…pk. We need to make sure p1, p2…pk as close as possible.

    But still we don’t know how many p we should use. For example, 36 = 6 * 6 = 2 * 18 = 2 * 3 * 2 * 3. Which we should use?

    First, we should discard 2 * 18 because we need to make sure p1 and p2 as close as possible. But how to choose from 6 * 6 or 2 * 3 * 2 * 3.

    We can use an easier example p1 * p2 = p1 * p3 * p4 = p1 * d * (p2/d) (Here p2 = p3 * p4 and d = p3, p2/d = p4, p2 > d = p3, p2 > p2/d = p4)

    p2 >= d + p2/d because p2 * d >= d^2 + p2.

    As a result, we also need to decompose the number N as much as possible.

    So, each loop, we start from i = 2 to get the smallest possible candidate number. These numbers are also the closest number we could find.

    I hope it is helpful. (I don't know how to submit a code with a better format, sorry about it).
    '''
    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;
    }
    '''


Log in to reply
 

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