Medium
Related Topics: Math / Dynamic Programming
LeetCode Source

解題想法

題目要求我們找到最少步數可以完成 n 個 A 的可能性

這題的解法蠻特別的

此問題的解法等價於因式分解該數字之合

比如說n = 18，因為18 = 2*3*3

則答案就是8=2+3+3

所以我們必須先完成一個子程式 f 包我們做因式分解

在因式分解時，while中止條件是num < 1

而因式是從k開始，k=i+2，此時k=2

若k可以整除，則num /= k，且存入factor

之後break，確保下次因式是從當次因式開始

最後sum(f)，得到所有因式之合

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Python

class Solution:
    def minSteps(self, n: int) -> int:
        return sum(self.f(n))

    def f(self, num):
        factor = []
        while num > 1:
            for i in range(num-1):
                k = i + 2
                if num % k == 0:
                    factor.append(k)
                    num = int(num / k)
                    break
        return factor

C++

class Solution {
public:
    int minSteps(int n) {
        vector<int> f;

        while (n > 1) {
            for (int i = 2; i <= n; i++) {
                if (n % i == 0) {
                    f.push_back(i);
                    n /= i;
                    break;
                }
            }
        }

        return accumulate(f.begin(), f.end(), 0);
    }
};