# Java Solution via Prime Factorization and the Math Proof

• 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;
}
//
``````

• 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).

• Great solution, thanks for sharing

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

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