650. 2 Keys Keyboard¶

650. 2 Keys Keyboard¶

Tags: Medium Math Dynamic Programming

Links: https://leetcode-cn.com/problems/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].

class Solution {
public:
    int minSteps(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int cnt = 0;
        for (int i = 2; i <= n; ++i) {
            while (n % i == 0) {
                cnt += i;
                n /= i;
            }
        }

        return cnt;
    }
};

相当于求所有质因子的和。

考虑经过一系列操作使得出现n个A，可以把这一系列过程写成字母表示，比如n = 3的时候：

CPP 代表复制一次，拷贝两次

那么得到最终的结果n，假设经过下列操作：

CPP     CPP...PPP   CPPP...PPP

我们把上面进行分组，每个组里面就是一次C，多次P，设每个组的长度为 $l_i$ ，则显然有： $$ n = l_1 \times l_2 \times l_3 \cdots \times l_n $$ 则总的操作次数是 $\sum_{i=0}^n l_i$ 。现在需要考虑 $l_i$ 怎么划分，如果n是质数，显然一个一个的打印是最快的，最少操作数就是n，如果是合数，那么存在 $n = p \times q$ ，显然 $p \geq 2, q \geq 2$ 。则显然有： $$ (p - 1) \times (q - 1) \geq 1 \ \therefore p + q \leq p \times q $$ 如果因子p或q还可以继续分解，那么根据上面的推导，操作数还是会进一步的减小，那么当变成质因子的时候，将无法分解，假设质因子是k，则操作代表1次赋值，k - 1次粘贴。

所以最终的结果就是所有质因子的和。

时间复杂度 $O(\sqrt n)$ 。