LeetCode Ts-2507. Smallest Value After Replacing With Sum of Prime Factors

    AllenLi
    CodingLeetCode Js-Math

    You are given a positive integer n.
    Continuously replace n with the sum of its prime factors.
    Note that if a prime factor divides n multiple times, it should be included in the sum as many times as it divides n.
    Return the smallest value n will take on.

    你給予一個正整數 n。
請用 n 的質因數之和來不斷的替代它。
這注意，如果某個質因數能多次整除 n，則在求和時應將它重複計入與其出現次數相同。
返回 n 在過程中能達到的最小值。

    Example 1:

    Input: n = 15
Output: 5
Explanation: Initially, n = 15.
15 = 3 * 5, so replace n with 3 + 5 = 8.
8 = 2 * 2 * 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 * 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.

    Example 2:

    Input: n = 3
Output: 3
Explanation: Initially, n = 3.
3 is the smallest value n will take on.

    Solution:
    這題可以當作是數學問題，我們不斷將 n 替換成它的質因數和，直到結果不再改變。
    我們在 while(true) 迴圈中，從最小質數 2 開始試除，
    對每個可能的質因數累加到 sum，並將 temp 除以該質因數。
    當除完之後，如果 temp > 1，表示 temp 本身是一個質數，也要加入 sum。
    當 sum 等於原本的 n 時，即可返回最小值。

    Code 1: BigO(n​ * log n)

    function smallestValue(n: number): number {
    while (true) {
        let original: number = n;
        let sum: number = 0;
        let temp: number = n;

        for (let i = 2; i * i <= temp; i++) {
            while (temp % i === 0) {
                sum += i;
                temp /= i;
            }
        }   
        if (temp > 1) sum += temp;
        if (sum === original) return n;
        n = sum;
    }
};

    FlowChart:
    Example 1

    Input: n = 15

original = 15, sum = 0, temp = 15
i = 2, temp % i = 1, sum = 0 temp = 15
i = 3 temp % i = 0, sum = 3 temp = 5
n = sum = 8

original = 8, sum = 0, temp = 8
i = 2 temp % i = 0, sum 6 temp 1
n = sum = 6

original = 6, sum = 0, temp = 6
i = 2 temp % i = 0, sum 2 temp 3
original 5 sum 0 temp 5
i = 2 temp % i = 1, sum 0 temp 5
n = sum = 5

original = 5, sum = 0, temp = 5
i = 2 temp % i = 1 sum 0 temp 5
n = sum = 5

return n // 5;

    Example 2

    Input: n = 3
original = 3, sum = 0, temp = 3
n = sum = 3

    Related Posts