判斷一個整數
n是否為醜數。醜數是指質因數只包含 2、3、5 的正整數。1 通常被視為醜數。
Example:
Input: n = 6 Output: true (6 = 2 x 3)
Intuition
TIP
核心思路：不斷除以 2、3、5，如果最終結果為 1 則是醜數。
- 醜數的定義是質因數只包含 2、3、5
- 反覆將 n 除以 2、3、5，直到不能再除
- 最後若 n == 1 則所有質因數都已被消除，是醜數
- 注意：n <= 0 不是醜數
Approaches
⭐ 1. Repeatedly Divide by Prime Factors — O(log n) / O(1)
- Idea: 依序除以 2、3、5 直到無法整除，最終檢查是否為 1
- Time:
O(log n)- 每次至少除以 2 - Space:
O(1)
class Solution {
fun isUgly(n: Int): Boolean {
if (n <= 0) return false
var num = n
for (factor in intArrayOf(2, 3, 5)) {
while (num % factor == 0) {
num /= factor
}
}
return num == 1
}
}2. Recursive — O(log n) / O(log n)
- Idea: 用遞迴表達除法過程
- Time:
O(log n) - Space:
O(log n)- 遞迴堆疊
class Solution {
fun isUgly(n: Int): Boolean {
if (n <= 0) return false
if (n == 1) return true
return when {
n % 2 == 0 -> isUgly(n / 2)
n % 3 == 0 -> isUgly(n / 3)
n % 5 == 0 -> isUgly(n / 5)
else -> false
}
}
}🔑 Takeaways
- Pattern: 質因數分解——反覆除以目標質因數直到無法整除
- Key trick: 用 for 迴圈遍歷質因數清單比寫三個 while 更簡潔；先排除 n <= 0 的邊界情況