假设我们在文本编辑器中只有一个字符“ A”。对于每个步骤,我们可以对该字母执行两项操作-
全部复制-我们可以复制记事本中显示的所有字符
粘贴-我们可以粘贴上次复制的字符。
现在假设我们有一个数字n。通过执行允许的最小步骤数,我们必须在记事本上精确得到n个“ A”。我们必须以最少的步数找到结果以获得n'A'。因此,如果给定的n为3,则答案将为3,因此最初只有一个“ A”,现在将其复制并粘贴,因此现在将为“ AA”。现在我们可以再次粘贴,因此将放置一个“ A”。这样我们将获得“ AAA”。
为了解决这个问题,我们将遵循以下步骤-
ret:= 0
对于2到n范围内的k
ret:= ret + k和n:= n / k
而n mod k不为0
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int minSteps(int n) { int ret = 0; for(int k = 2; k <= n; k++){ for(; n % k == 0; ret += k, n /= k); } return ret; } }; main(){ Solution ob; cout << (ob.minSteps(10)); }
10
输出结果
7