LeetCode 326 Power of Three
概述
https://leetcode.com/problems/power-of-three/
递归法
时间复杂度 O(logn)。
class Solution {
public:
bool isPowerOfThree(int n) {
if (n == 0) return false;
if (n == 1) return true;
if (n % 3 != 0) return false;
return isPowerOfThree(n / 3);
}
};
质数法
利用其质数的性质,
public class Solution {
public boolean isPowerOfThree(int n) {
// 1162261467 is 3^19, 3^20 is bigger than int
return ( n > 0 && 1162261467 % n==0);
}
Links: leetcode-326-power-of-three