Question

Formatted question description: https://leetcode.ca/all/650.html

 650. 2 Keys Keyboard

 Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

 Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
 Paste: You can paste the characters which are copied last time.


 Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

 Example 1:

 Input: 3
 Output: 3
 Explanation:
     Intitally, we have one character 'A'.
     In step 1, we use Copy All operation.
     In step 2, we use Paste operation to get 'AA'.
     In step 3, we use Paste operation to get 'AAA'.


 Note:
    The n will be in the range [1, 1000].

Algorithm

This question only gave us two buttons. If you can only choose two buttons, then I will definitely have to copy and paste. These two buttons are in hand, I have the world! ! ! Sure enough, this question is to give the two buttons of copy and paste, and then give an A.

These two keys are used to print out n A. Note that when copying, all are copied, and you cannot select parts to copy. Then copy and paste are both operation steps, ask how many steps are needed to print out n A.

For this kind of problem with obvious recurrence characteristics, you must have a vague feeling, and you must try recursion and DP. Recursive solutions are generally close to brute force search, but sometimes they can be optimized to pass OJ. If recursion is not possible, then DP can be solved generally.

Another point is that for this kind of problem, finding the law is the most important. DP must find the state transition equation, and if the inner connection cannot be found, then the state transition equation is more difficult to write. So, start with a simple example and try to find a pattern:

When n = 1, there is already an A, no other operations are needed, return 0

When n = 2, need to copy once, paste once, return 2

When n = 3, you need to copy once and paste twice, return 3

When n = 4, there are two ways to do this,

  • one is to copy once and paste three times, a total of 4 steps,
  • the other is to copy once, paste once to get AA, then copy again, paste once to get AAAA, both methods return 4

When n = 5, you need to copy once, paste four times, and return to 5.

When n = 6, you need to copy once and paste twice to get AAA, and copy again and paste once to get AAAAAA, 5 steps in total, return to 5.

By analyzing the above 6 simple examples, we can conclude some rules.

  1. First of all, for any n (except 1), the worst case is to use n steps, no more than n steps,
  2. but it may be less than n steps. For example, when n=6, only 5 steps are used. After careful analysis, it is first spelled as AAA, and then copied and pasted to AAAAAA.
  3. So under what circumstances can this method be used to reduce steps? Analysis found that the length of the small module must be divisible by n in order to be split. For n=6, we can actually print AA first, then copy and paste it twice, and get 5 again.

At this point in the analysis, the idea of solving the problem should be clearer, find out all the factors of n, and then this factor can be used as the number of modules, and then calculate the length of the module n/i, call recursion, and add the number of modules i To update the result res.

Code

Java

  • 
    public class two_Keys_Keyboard {
        class Solution {
            public int minSteps(int n) {
                if (n == 1) return 0;
                int res = n;
    
                // factor `i` can be used as the number of modules
                for (int i = n - 1; i > 1; --i) {
                    if (n % i == 0) {
                        res = Math.min(res, minSteps(n / i) + i);
                    }
                }
                return res;
    
            }
        }
    
        class Solution_dp {
            public int minSteps(int n) {
                int[] dp = new int[n + 1];
                for (int i = 2; i <= n; ++i) {
                    dp[i] = i;
                    for (int j = i - 1; j > 1; --j) {
                        if (i % j == 0) {
                            dp[i] = Math.min(dp[i], dp[j] + i / j);
                        }
                    }
                }
                return dp[n];
    
            }
        }
    
    
        class Solution_bruteForce {
            public int minSteps(int n) {
                int ans = 0, d = 2;
                while (n > 1) {
                    while (n % d == 0) {
                        ans += d;
                        n /= d;
                    }
                    d++;
                }
                return ans;
            }
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/2-keys-keyboard/
    // Time: O(N^(3/2))
    // Space: O(N)
    class Solution {
    public:
        int minSteps(int n) {
            vector<int> dp(n + 1, INT_MAX);
            dp[1] = 0;
            for (int i = 2; i <= n; ++i) {
                for (int j = 1, end = sqrt(i); j <= end; ++j) {
                    if (i % j) continue;
                    dp[i] = min({ dp[i], dp[j] + i / j, j == 1 ? INT_MAX : (dp[i / j] + j) });
                }
            }
            return dp[n];
        }
    };
    
  • """
    1. group operations as ([^C][^V][^V]...[^V]) that has in total k operations and it gets k * # of A
    2. n can be written as x_1 * x_2 * ... * x_N
    3. then total operations # = x_1 + x_2 + ... + x_N
    4. since p * q >= p + q for integers > 1, to min the result
    5. decomposite x_1 to x_N to min the sum
    """
    
    
    class Solution(object):
      def _minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
          return 0
        for i in range(2, int((n + 1) ** 0.5) + 1):
          if n % i == 0:
            return i + self.minSteps(n / i)
        return n
    
      def minSteps(self, n):
        def factor(n):
          d = 2
          while d * d <= n:
            while n % d == 0:
              n /= d
              yield d
            d += 1
          if n > 1:
            yield n
    
        return sum(factor(n))
    
    

All Problems

All Solutions