Skip to content

650. 2 Keys Keyboard 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int minSteps(int n) {
    if (n <= 1)
      return 0;

    // dp[i] := the minimum steps to get i 'A's
    vector<int> dp(n + 1);

    // Copy 'A', then paste 'A' i - 1 times.
    iota(dp.begin(), dp.end(), 0);

    for (int i = 2; i <= n; ++i)
      for (int j = i / 2; j > 2; --j)
        if (i % j == 0) {
          dp[i] = dp[j] + i / j;  // Paste dp[j] i / j times.
          break;
        }

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public int minSteps(int n) {
    // dp[i] := the minimum steps to get i 'A's
    int[] dp = new int[n + 1];

    for (int i = 2; i <= n; ++i) {
      dp[i] = i; // Copy 'A', then paste 'A' i - 1 times.
      for (int j = i / 2; j > 2; --j)
        if (i % j == 0) {
          dp[i] = dp[j] + i / j; // Paste dp[j] i / j times.
          break;
        }
    }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def minSteps(self, n: int) -> int:
    if n <= 1:
      return 0

    # dp[i] := the minimum steps to get i 'A's
    # Copy 'A', then paste 'A' i - 1 times.
    dp = [i for i in range(n + 1)]

    for i in range(2, n + 1):
      for j in range(i // 2, 2, -1):
        if i % j == 0:
          dp[i] = dp[j] + i // j  # Paste dp[j] i / j times.
          break

    return dp[n]