LeetCode Power of Three：判斷 3 的冪 — 循環法與數學法

題目描述

給定整數 n，判斷是否存在整數 k 使得 n = 3^k。進階：不使用循環/遞歸。

解法一：循環除以 3

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    while (n % 3 == 0) n /= 3;
    return n == 1;
}

解法二：數學法（無循環）

32 位有符號整數最大的 3 的冪是 3^19 = 1162261467。若 n > 0 且 1162261467 % n == 0，則 n 是 3 的冪。

bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

複雜度分析

• 循環法：時間 O(log₃ n)，空間 O(1)。
• 數學法：時間 O(1)，空間 O(1)。