public int minSteps(int n) {
int[] dp = new int[n+1];
for (int i = 2; i <= n; i++) {
dp[i] = i;
for (int j = i1; j > 1; j) {
if (i % j == 0) {
dp[i] = dp[j] + (i/j);
break;
}
}
}
return dp[n];
}
Java DP Solution



You don't even need
dp[i] = i
public int minSteps(int n) { int[] dp = new int[1001]; for (int i = 2; i <= n; i++) { // subproblem dp[i] := minSteps(i) for (int j = 2; j <= i; j++) { // j := use j steps to create j copies if (i % j == 0) { dp[i] = j + dp[i / j]; break; } } } return dp[n]; }

By far, I tested and found below solution is the fastest....
public int minSteps(int n) { if(n<=5)return n<=1?0:n; int[] dp=new int[n+1]; dp[0]=0; dp[1]=0; dp[2]=2; for(int i=3;i<dp.length;i++){ dp[i]=i; for(int j=2;j<=Math.sqrt(i);j++){ if(j*(i/j)==i){ dp[i]=Math.min(dp[i],dp[i/j]+j); break; } } } return dp[n]; }

Pure loop solution is the fastest I found, only took 9 ms
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; }


@yuxiangmusic This is far better than OP's solution. The recursive relation is about n's factors, so it doesn't make sense to memoize all the way from 1 to n.


@xuanyue_vol The algorithm iterates through the factors backwards, selecting the greatest one first. This ensures that the amount of copy/paste operations is minimal. For instance, consider the number
8
.You can do it in three ways:
 Copy (1A), paste (2A), paste (3A), paste (4A), paste (5A), paste (6A), paste (7A), paste (8A)
 Copy (1A), paste (2A), copy (2A), paste (4A), paste (6A), paste (8A)
 Copy (1A), paste (2A), paste (2A), copy (4A), paste (8A)
Because
4
is8
's highest factor, it will give the optimal solution.

@shreydesai So this "iterates through the factors backwards, greatest one first. This ensures that the amount of copy/paste operations is minimal."
This is where I'm not getting 100% confidence by a simple example.
For an integer n and its largest factor k1 and a smaller factor k2, how can we guarantee (n/k1) + solve(n/k1) is guaranteed to be larger than (n/k2) + solve(n/k2)? could it be possible that n/k1 < n/k2 but solve(n/k1) > solve(n/k2)?

Could I ask what is the run time complexity, which is required in real interview?
I got downvoted to claim it is O(n^2). Could someone provide a better analysis please?
Btw, here is my O(n^0.5) solution. O(n^0.5) solutionclass Solution { public: int minSteps(int n) { int ans = 0; for (int i = 2; i <= sqrt(n); i++) { while (n%i == 0) { ans += i; n /= i; } } if (n > 1) ans += n; return ans; } };

@shreydesai said in Java DP Solution:
"Copy (1A), paste (2A), paste (2A), copy (4A), paste (8A)"
This won't work, should be :
Copy (1A), paste (2A), paste(3A)

For dp[i] = dp[j] + i/j
Example:
dp[100] = dp[20] + 100/20 = 9 + 5 = 14
= dp[25] + 100/25 = 10 + 4 = 14
= dp[50] + 100/50 = 12 + 2 = 14That's why once we found one solution and break immediately.
I'm kind of confused, why they all add up to the same number, whichever dividing factor I chose. Any mathematics behind?