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


  • 21
    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 }.inject(0, :+)
    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;
        }
    

  • 0
    F

    This is greedy approach, am i right?


  • 0
    Y
    This post is deleted!

Log in to reply
 

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