Welcome to Subscribe On Youtube

650. 2 Keys Keyboard

Description

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

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

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

 

Example 1:

Input: n = 3
Output: 3
Explanation: Initially, 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'.

Example 2:

Input: n = 1
Output: 0

 

Constraints:

  • 1 <= n <= 1000

Solutions

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 pattern 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.

  • class Solution {
    public int minSteps(int n) {
        int res = 0;
        for (int i = 2; n > 1; ++i) {
            while (n % i == 0) {
                res += i;
                n /= i;
            }
        }
        return res;
    }
}


  • class Solution {
public:
    vector<int> f;

    int minSteps(int n) {
        f.assign(n + 1, -1);
        return dfs(n);
    }

    int dfs(int n) {
        if (n == 1) return 0;
        if (f[n] != -1) return f[n];
        int ans = n;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                ans = min(ans, dfs(n / i) + i);
            }
        }
        f[n] = ans;
        return ans;
    }
};

  • class Solution:
    def minSteps(self, n: int) -> int:
        @cache
        def dfs(n):
            if n == 1:
                return 0
            i, ans = 2, n
            while i * i <= n:
                if n % i == 0:
                    # factor `i` can be used as the number of modules
                    # n // i, length of the module `n/i`
                    ans = min(ans, dfs(n // i) + i)
                i += 1
            return ans

        return dfs(n)

############

# iteration
class Solution:
    def minSteps(self, n: int) -> int:
        res = 0
        i = 2
        while n > 1:
            while n % i == 0:
                res += i
                n //= i
            i += 1
        return res

############

"""
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
"""

'''
`yield` is a keyword that is used like return, except the function will return a generator.

https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python
'''

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


  • func minSteps(n int) int {
	f := make([]int, n+1)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(n int) int {
		if n == 1 {
			return 0
		}
		if f[n] != -1 {
			return f[n]
		}
		ans := n
		for i := 2; i*i <= n; i++ {
			if n%i == 0 {
				ans = min(ans, dfs(n/i)+i)
			}
		}
		return ans
	}
	return dfs(n)
}

All Problems

All Solutions