326_PowerofThree - a920604a/leetcode GitHub Wiki
title: 326. Power of Three
- Bit Manipulation
categories: leetcode
comments: false
tags:problem
solution
option 1 iterative and recursive
class Solution {
public:
bool isPowerOfThree(int n) {
if(n<1) return false;
while(n%3==0) n/=3;
return n==1;
}
};
class Solution {
public:
bool isPowerOfThree(int n) {
if(n<1) return false;
if(n%3==0) return isPowerOfThree(n/3);
return n==1;
}
};
因為在[0,2^31-1]
之間最大的三次方數為3^19 = 1162261467
return (n > 0 && 1162261467 % n == 0);
option 2 - 換底公式
class Solution {
public:
bool isPowerOfThree(int n) {
return (n>0 && int(log10(n)/log10(3))-log10(n)/log10(3)==0 );
}
};
analysis
- time complexity
O(1)
- space complexity
O(1)