Loop best case log(n), no DP, no extra space, no recursion, with explanation


  • 29
    Y

    We look for a divisor d so that we can make d copies of (n / d) to get n

    The process of making d copies takes d steps (1 step of Copy All and d - 1 steps of Paste)

    We keep reducing the problem to a smaller one in a loop.

    The best cases occur when n is decreasing fast, and method is almost O(log(n))

    For example, when n = 1024 then n will be divided by 2 for only 10 iterations, which is much faster than O(n) DP method.

    The worst cases occur when n is some multiple of large prime, e.g. n = 997 but such cases are rare.

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

  • 0
    C

    @yuxiangmusic did this actually pass all tests?


  • 0
    H

    @c8b2b9ef It does - had the same solution.


  • 0

    As n <= 1000, this method is not taking much more time than the DP solution. In which case, DP has to loop from 1 to n.


  • 1

    Ruby version.

    require 'prime'
    
    def min_steps(n)
      n.prime_division.map { |p, e| p * e }.sum
    end
    

  • 1
    M

    If add an if case, in the for loop, go from 2 to sqrt(n) is enough. The codes are as follows

    public int minSteps(int n) {
            int s = 0;
            for (int d = 2; d <= Math.sqrt(n); d++) {
                while (n % d == 0) {
                    s += d;
                    n /= d;
                }
                
            }
            if (n!=1){
                s+=n;
            }
            return s;
        }
    

  • 1
    F

    This is greedy approach, am i right?


  • 0
    Y
    This post is deleted!

  • 0
    W

    I think this is greedy algorithm. Can anyone prove this algorithm is correct?


Log in to reply
 

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