326 Power of Three 3的冪
Description:
Given an integer, write a function to determine if it is a power of three.
Example :
Example 1:
Input: 27
Output: true
Example 2:
Input: 0
Output: false
Example 3:
Input: 9
Output: true
Example 4:
Input: 45
Output: false
Follow up:
Could you do it without using any loop / recursion?
題目描述:
給定一個(gè)整數(shù)扳抽,寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 3 的冪次方贤旷。
示例 :
示例 1:
輸入: 27
輸出: true
示例 2:
輸入: 0
輸出: false
示例 3:
輸入: 9
輸出: true
示例 4:
輸入: 45
輸出: false
進(jìn)階:
你能不使用循環(huán)或者遞歸來(lái)完成本題嗎触创?
思路:
- 循環(huán)判斷 n % 3 == 0, 執(zhí)行 n /= 3直到 n == 1
- 遞歸, 方法同 1
- 注意到 3是質(zhì)數(shù), 所以 3的冪只有 3的 n次方的因數(shù)
如 9只有 1、3曲尸、9三個(gè)因子
int范圍內(nèi)最大的 3的冪為 1162261467(3 ^ 19)
3的冪一定是該數(shù)的因子, 即 1162261467 % n = 0
時(shí)間復(fù)雜度O(1), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
bool isPowerOfThree(int n)
{
return n > 0 and (1162261467 % n) == 0;
}
};
Java:
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n) == 0;
}
}
Python:
class Solution:
def isPowerOfThree(self, n: int) -> bool:
return n > 0 and (1162261467 % n) == 0