650. 2 Keys Keyboard

Description

image-20210822003910383

Solution

  • O(n^2), search from 1 to i-1 to find the smallest operation number for dp[i]

  • O(sqrt(n)), all the operations sequences are like : CPPPCPPPPCP..., can be divided into groups (CPPP)(CPP)(CP)…. .If we have each group’s length like g1, g2,g3..., so after first group, there are g1 A’s, after second group g1 * g2 A’s…

    We want have N = g1 * g2 * g3...*gn A’s, if gi can be divided into product of other two numbers, denote as gi = p * q, so it can be divided into 2 group, first contains 1C and p-1P, second one contains 1C and q-1P. It is easy to prove that after dividing, we need fewer steps.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int minSteps(int n) {
        if(n==1)
            return 0;
        int f = getFactors(n);
        if(f == 1)
            return n;
        vector<int> dp(f+1,INT_MAX);
        dp[1] = 0;
        int res = INT_MAX;
        for(int i = 2; i <= f; i++){
            int sf = getFactors(i);
            for(int j = 1; j <= sf; j++){
                if(i % j == 0){
                    dp[i] = min(dp[i], dp[j] + i/j);
                }
            }
            if(n % i == 0){
                res = min(res, dp[i] + n/i);
            }
        }
        return res;
    }
    
    int getFactors(int n){
        for(int i = n-1; i >= 1; i--){
            if(n%i==0)
                return i;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11

class Solution(object):
    def minSteps(self, n):
        ans = 0
        d = 2
        while n > 1:
            while n % d == 0:
                ans += d
                n /= d
            d += 1
        return ans