2 Keys Keyboard LeetCode solution in C++

1
class Solution {
2
 public:
3
  // See the solution for this explanation
4
  int byPrimeFactorization(int n) {
5
    if (n == 1) return 0;
6
    if (n == 2) return 2;
7
    int factor = 2, ans = 0;
8
    while (n > 1) {
9
      while (n % factor == 0) {
10
        ans += factor;
11
        n /= factor;
12
      }
13
      factor++;
14
    }
15
    return ans;
16
  }
17

18
  int byDp(int n) {
19
    vector<int> dp(1001, INT_MAX);
20
    dp[0] = dp[1] = 0;
21
    dp[2] = 2, dp[3] = 3;
22
    for (int i = 4; i <= n; i++) {
23
      dp[i] = i;                         // maximum number of operations required will be i
24
      for (int j = 2; j <= i / 2; j++) { // we copy and paste j A's till we have i A's
25
        int x = i - j;    // we already have j A's in our stream, so remaining = i - j
26
        if (x % j == 0) { // if remaining number of A's is a multiple of J
27
          dp[i] = min(dp[i], dp[j] + 1 + (x / j)); // 1 operation to copy, x / j to
28
                                                   // paste, dp[j] for getting j A's
29
        }
30
      }
31
    }
32
    return dp[n];
33
  }
34

35
  int minSteps(int n) {
36
    return byPrimeFactorization(n);
37
  }
38
};