326. Power of Three

  • 39.7%

https://leetcode.com/problems/power-of-three/#/description

Given an integer, write a function to determine if it is a power of three.

Follow up:

Could you do it without using any loop / recursion?


方法一:

我的代码实现:

Oct 23, 2017

1
2
3
4
5
6
7
8
class Solution {
int max3power = 1162261467;
public:
bool isPowerOfThree(int n) {
if(n<=0 || n>max3power) return false;
return max3power%n == 0;
}
};

https://discuss.leetcode.com/topic/39293/without-log-and-o-1

Without log and O(1).

1
2
3
4
5
6
7
8
9
class Solution {
public:
int const Max3PowerInt = 1162261467; // 3^19, 3^20 = 3486784401 > MaxInt32
int const MaxInt32 = 2147483647; // 2^31 - 1
bool isPowerOfThree(int n) {
if (n <= 0 || n > Max3PowerInt) return false;
return Max3PowerInt % n == 0;
}
};

Typically, Log(x, y) is not O(1), it should be O(ln(N)), which just hides the loop/recursion .


https://discuss.leetcode.com/topic/34990/1-line-c-no-recursion-loop

1 line C++ no recursion/loop

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfThree(int n) {
return fmod(log10(n)/log10(3), 1)==0;
}
};

https://discuss.leetcode.com/topic/33526/one-line-cheating

One line (cheating)

1
2
3
4
5
public class Solution {
public bool IsPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
}

https://discuss.leetcode.com/topic/43385/c-solution-no-loop-recursion

C++ solution no loop / recursion

1
2
3
4
5
bool isPowerOfThree(int n) {
if (n<=0) return false;
int t = pow(3,(int)(log(INT_MAX)/log(3)));
return (t%n == 0);
}

t is maximum power of three


https://discuss.leetcode.com/topic/36289/python-o-1-solution-96-6

Python O(1) Solution 96.6%

1
2
3
class Solution(object):
def isPowerOfThree(self, n):
return n > 0 and 1162261467 % n == 0
谢谢你,可爱的朋友。