Leetcoce 650: 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/description/

Notes:

This question is looking for the minimum distance from one pointer to another. So in general BFS should work, but there are other ways to solve this problem as well.

There are two key two parameters: one is the value (or the length), the other is the length of pasting.

In order to code easier, below I choose dfs + memorization.

The key relation is memo[val][paste] = 1 + min(memo[val + paste][paste], memo[val][val])

Of course, we have to make sure, we will not go back directly to the original position, which means: when paste == 0, the first term in the min() will not be considered; when paste == val, the second term will not be considered.

See the code below:

class Solution {
public:
    int minSteps(int n) {
    //    if(n==1) return n;
        int val = 1, last = 0;
        vector<vector<int>> memo(n+1, vector<int>(n+1, -1));
        return dfs(val, last, n, memo);
    }
private:
    int dfs(int v, int la, int n, vector<vector<int>>& memo) {
        if(v == n) return 0; //good end
        if(v > n) return n; //dead end
        if(memo[v][la] != -1) return memo[v][la];
        int t = n;
        if(la>0) t = min(t, 1 + dfs(v+la, la, n, memo));
        if(la != v) t= min(t, 1 + dfs(v, v, n, memo));
        return memo[v][la] = t;
    }
};

The above time complexity is O(n*n), which can pass the OJ, but it ranks ~ 10%.

This question is labeled as Math, which means there may be faster ways.

After searching online, it turns out that we just need to find the prime factors of n! The arguments are listed below:

https://leetcode.com/problems/2-keys-keyboard/discuss/105928/JavaC++-Clean-Code-with-Explanation-4-lines-No-DP

It take 2 ops to double, 3 ops to triple, ...
if n % 2 == 0, then f(n) = f(n/2) + 2
if n % 3 == 0, then f(n) = f(n/3) + 3
2 * 2 = 2 + 2; 2 * 3 > 2 + 3; 4 * 4 > 4 + 4; so it is always better to divide whenever possible.
now it became a problem for finding all possible factors

See the code below:

class Solution {
public:
    int minSteps(int n) {
        if(n==1) return 0;
        for(int i=2; i<n; ++i) {
            if(n%i == 0) return i + minSteps(n/i);
        }
        return n;
    }
};