clueless coding // TODO: be smarter

LeetCode 650. 2 Keys Keyboard: Java Solution



Problem Statement


Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy: 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’.

Function Signature (Java):
  int minSteps(int n)

Inputs:
  3

Outputs:
  3

Intitally, we have a single 'A'.
In step 1, we copy:
  A
In step 2, we paste:
  AA
In step 3, we paste again:
  AAA



TL;DR Code Solution


public int minSteps(int n) {
    int[] dp = new int[n+1];

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

        }
    }
    return dp[n];
}