Java Solution via Prime Factorization and the Math Proof


  • 1
    R

    Inspired by the greedy algorithm posted by https://discuss.leetcode.com/topic/97623/loop-best-case-log-n-no-dp-no-extra-space-no-recursion-with-explanation. Here I show a proof for it.

    [Theorem] Let f(n) be the result of this problem. If n>=2 and n=product{pi^ei, for 1<=i<=t} is the prime factorization of n, where pi's are distinct primes and ei's are positive integers, for 1<=i<=t, then f(n)=sum{pi*ei, for 1<=i<=t}.

    [Proof of Theorem] We prove by induction on n. It is clear for n=2. Assuming that the theorem is true for all positive integer >=2 and <n, we show the case for n.

    If n is a prime, then to obtain n A's, there is ONLY one way, i.e., by CopyAlling 1 'A', and Pasting for (n-1) times (there is no other way to duplicate a string 'AA...A' to obtain n A's). Therefore, f(n)=1+n-1=n, which is the only prime factor of n.

    Otherwise, let n=product{pi^ei, for 1<=i<=t} be the prime factorization of n. Let ni=n/pi, for 1<=i<=t. To obtain n A's, there are exactly t+1 ways:

    The 1st way is to CopyAll 1 'A', and Paste for (n-1) times, which costs n steps;

    The other t ways are: For 1<=i<=t, to form ni A's by f(ni) steps (noticing that it is the # of min steps to obtain ni A's), then CopyAll ni 'A's, and Paste for n/ni-1=pi-1 times, totally costing f(ni)+1+pi-1=f(ni)+pi steps.

    Since 2<=ni<n, and ni=n/pi = pi^(ei-1) * product{pj^ej, for 1<=j<=t, j!=i}, by the induction hypothesis,

    f(ni) = pi*(ei-1) + sum{pj*ej, for 1<=j<=t, j!=i}.

    Hence, each of the t ways costs f(ni)+pi = sum{pi*ei, for 1<=i<=t}.

    Therefore, f(n) must be min(n, sum{piei, for 1<=i<=t}), clearly n=product{pi^ei, for 1<=i<=t} > sum{piei, for 1<=i<=t}, when n is not a prime. The case for n is proved.

    By the induction principle, the theorem holds. [End]

    		public int minSteps(int n) {
    			int res = 0;
    			for (int d = 2; d <= n; d++) {
    				while (n % d == 0) {
    					res += d;
    					n /= d;
    				}
    			}
    
    			return res > 0 || n == 1 ? res : n;
    		}
    		//
    

  • 0
    R

    I should've said n=product{pi^ei, for 1<=i<=t} >= sum{piei, for 1<=i<=t}, when n is not a prime (for the case n=4=2*2, which is the only case the equality holds).


  • 0
    C

    Great solution, thanks for sharing


  • 0
    S

    @rikimberley What is the time complexity of this algorithm? Cool analysis though!


Log in to reply
 

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