LeetCode //C - 650. 2 Keys Keyboard

650. 2 Keys Keyboard

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
  

From: LeetCode
Link: 650. 2 Keys Keyboard

---

Solution:

Ideas:

• If n is 1, return 0.
  
• Otherwise, find the smallest factor i of n, and return i + minSteps(n / i).
  
• If n is prime, the smallest factor is n itself.
  

Code:

1. int minSteps(int n) {
2.     int res = 0;
3.     for (int i = 2; i <= n; ++i) {
4.         while (n % i == 0) {
5.             res += i;
6.             n /= i;
7.         }
8.     }
9.     return res;
10. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。