Repository navigation
Expand file tree
/
Copy pathPowerOfThree.cpp
More file actions
66 lines (57 loc) · 1.83 KB
/
Copy pathPowerOfThree.cpp
File metadata and controls
66 lines (57 loc) · 1.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// Source : https://leetcode.com/problems/power-of-three/
// Author : Hao Chen
// Date : 2016-01-14
/***************************************************************************************
*
* 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?
*
* Credits:Special thanks to @dietpepsi for adding this problem and creating all test
* cases.
*
***************************************************************************************/
class Solution {
public:
bool isPowerOfThree(int n) {
return isPowerOfThree03(n); //140ms
return isPowerOfThree02(n);//130ms
return isPowerOfThree01(n); //140ms
return isPowerOfThree_loop(n); //136ms
return isPowerOfThree_recursive(n); //168ms
}
bool isPowerOfThree03(int n) {
double logRes = log10(n)/log10(3);
return (logRes - int(logRes) == 0);
}
bool isPowerOfThree02(int n) {
return n>0 ? (1162261467%n==0) : false;
}
void init(unordered_map<int, bool>& power ){
int p = 1;
power[1]=true;
while(1){
p *= 3;
power[p] = true;
if (p > INT_MAX/3) break;
}
}
bool isPowerOfThree01(int n) {
static unordered_map<int, bool> power;
if (power.size()==0) init(power);
return power.find(n) != power.end();
}
bool isPowerOfThree_loop(int n) {
for(;n>0;n /= 3){
if (n==1 || n==3) return true;
if (n%3 != 0) return false;
}
return false;
}
bool isPowerOfThree_recursive(int n) {
if ( n == 1 || n == 3) return true;
if ( n==0 || n%3 != 0 ) return false;
return isPowerOfThree_recursive(n/3);
}
};