Greedy or math?

• The place of making the last copy is crucial as once a copy is made, we can no longer use a buffer that is smaller than it. In order to get enough number of `A`s in minimum number of steps, we will try to make the paste as big as possible. So what's the largest paste can we make at a certain step?

The answer is "the largest we can use to complete the remaining". So every time we made a progress, we would make a decision: whether to `copy` what we've written or do not copy and use the current buffer. Since every time we made the copy, we were sure the buffer will be able to complete the remaining (i.e., it a factor of the remaining number of A we need), not making `copy` upper bounds the number of steps we need to complete the remaining. If we can use a larger buffer to fill the remaining more quickly, why not do it?

Does it look like a greedy algorithm? But the real underlying truth is to construct the largest factor.

``````public int minSteps(int n) {
int copy = 0;
int finish = 1;
int step = 0;
while (n - finish > 0) {
if ((n - finish) % finish == 0) {
step++;  //copy takes a step
copy = finish;
}
finish += copy;
step++;
}
return step;
}
``````

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