Today we share a topic about “copy” + “paste”. Let’s cut to the chase.

01. Topic analysis

Question 650: A keyboard with only two keys
Originally there was only one character ‘A’ on A notepad. You can do two things on the notepad at a time: Copy All: You can Copy All the characters in the notepad (partial copying is not allowed). Paste: You can Paste the last character you copied.

Given a number n. You need to print exactly n ‘as’ in notepad using the minimum number of operations. Output The minimum number of operations that can print n ‘A’.


Example 1:

Input: 3

Output: 3

Explanation:

Initially, we only had one character'A'.

Step 1, we use the Copy All operation.

In step 2, we use Paste to get it'AA'.

In step 3, we use Paste to get it'AAA'.

Copy the code


Description:

The value of n ranges from 1 to 1000.

02. Topic analysis

So the idea here is to figure out what happens when you copy and paste, and figure out how to form the smallest operand of N A’s.


Let’s start with the simplest one, if we’re given A number of 1, we don’t have to do anything, because there’s already an A on the panel.


So if we’re given a number of 2, then we need to do C minus P, two operations to get it.


So if we’re given a number of 3, then we need to do C, P, P, three operations to get it.


If we give the number 4, we find that it looks different. Because there are two ways to get there. (C – P – C – P)


Or (C-p-p-P)


But the steps are the same.


All right, that’s it. STOP! From the above analysis, we can at least observe that if I is prime, then how many times do I need to be pasted? That is, the number of prime numbers is itself. For example, two AS = 2, three as = 3, five as = 5.


What about composite numbers? The number of times a composite number is the sum of the operations required to factor it into its prime factors. Explain, what does that mean? Here’s an example:


For example, 30 can be decomposed into 325. What does that mean? Let’s demonstrate this: first copy 1 and paste it twice to get 3. And then I copy 3, and I paste it once to get 6. Then copy 6 and paste it four times to get 30. Total needs (CPPCPPP)


Note: this is directly equal to the sum of the number of prime factorization operations since each copy is required. And the order of decomposition does not affect the result.


Based on the above analysis, the analysis results are as follows:

1. The degree of a prime is itself.

2. Composite number is the sum of the number of operations to decompose it into all prime numbers that can no longer be decomposed.


03. Examples of Go language

After analysis, the code is as follows:

func minSteps(n int) int {

 res := 0

 for i := 2; i <= n; i++ {

  for n%i == 0 {

   res += i

   n /= i

  }

 }

 return res

}

Copy the code

Execution Result:


I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download