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


  • 34
    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?


  • 0
    T

    whats the complexity for worst case ? o(n) ?


  • 0

    @terminator123456 said in Loop best case log(n), no DP, no extra space, no recursion, with explanation:

    whats the complexity for worst case ? o(n) ?

    No, O(n).


  • 0
    T

    This is not real O(lg(n)) solution! It's O(n) on average

    A much faster solution is:

    public int minSteps(int n) {
        // list of primes that are not greater than SQRT(n) - in this case, n = 1000,000, SQRT(n) = 1000
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
                173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
                241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
                401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
                479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
                571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
                647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
                739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
                827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
                919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
        int ans = 0;
        for (int p : primes) {
            while ((n % p) == 0) {
                ans += p;
                n /= p;
            }
        }
        return ans + (n == 1 ? 0 : n);
    }
    

    To show the difference:

    public class TwoKeysKeyboard650 {
        public int minSteps(int n) {
            // list of primes that are not greater than SQRT(n) - in this case, n = 1000,000
            int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                    43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                    103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
                    173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
                    241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                    317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
                    401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
                    479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
                    571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643,
                    647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
                    739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823,
                    827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
                    919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
            int ans = 0;
            for (int p : primes) {
                while ((n % p) == 0) {
                    ans += p;
                    n /= p;
                }
            }
            return ans + (n == 1 ? 0 : n);
        }
    
        public int minSteps1(int n) {
            int s = 0;
            for (int d = 2; d <= n; d++) {
                while (n % d == 0) {
                    s += d;
                    n /= d;
                }
            }
            return s;
        }
    
        static public void main(String[] args) {
            TwoKeysKeyboard650 test = new TwoKeysKeyboard650();
            long max = 0l;
            for (int i = 1; i < 1000000; i++) {
                long start = System.currentTimeMillis();
                test.minSteps(i);
                // test.minStep1(i);
                max = Math.max(max, System.currentTimeMillis() - start);
            }
            System.out.println(max);
        }
    }
    

  • 0
    I

    You can just change

     for (int d = 2; d <= n; d++) {
    

    to

     for (int d = 2; d * d <= n; d++) {
    

    and add the remains in the end if the remains not equal to 1

    which makes the worst case complexity down to O(N ** 1/2)


Log in to reply
 

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