Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

650. Keyboard with only two keys

Originally the notepad had A single character ‘A’. You can do two things with the notepad at a time:

  • Copy All: Copies All characters in this notepad (not only some characters).
  • Paste: pastes the characters that were copied last time.

Given the number n, you need to print exactly n ‘A’ in notepad using the minimum number of operations. Returns the minimum number of operations that can print n ‘A’.

Example 1: Input: 3 Output: 3 Explanation: Initially, there is only one character 'A'. Step 1, use the Copy All operation. Step 2, use Paste to get 'AA'. Step 3, use the Paste operation to get 'AAA'. Example 2: Input: n = 1 Output: 0Copy the code

Their thinking

It’s optimal to split consecutive strings A each time if they’re multiples of two, because you only need to copy and paste two, and if they’re multiples of three, you need to copy and paste three. Therefore, we need to break the string into as many parts as possible, so we can start with 2,3,4… Always find the current string can be divided into several pieces. Therefore, we only need to use “trial division” to perform prime factorization of n and calculate the sum of all prime factors, which is the final answer.

code

class Solution {
    public int minSteps(int n) {

        int res=0;
        while(n>1)
        {
            for(int i=2; i<=n; i++)if(n%i==0)
                {
                    n/=i;
                    res+=i;
                    break; }}returnres; }}Copy the code
  • Time complexity: O(SQRT (n), is the time complexity of prime factorization.
  • Space complexity: O(1).