Greedy or math?


  • 0
    V

    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 As 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;
        }
    

Log in to reply
 

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