-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathPower of Three.java
More file actions
executable file
·98 lines (83 loc) · 2.18 KB
/
Copy pathPower of Three.java
File metadata and controls
executable file
·98 lines (83 loc) · 2.18 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
E
1516341495
tags: Math
方法1:
Power of 3: 3 ^ x == n ?
意思是 n / 3 一直除, 最后是可以等于1的, 那么就有了 n/=3, check n%3, 最后看结果是不是整除到1的做法. 用while loop.
方法2:
如果n是power of 3, 那么 3 ^ x的这个 x一定是个比n小的数字. 那么可以在 0 ~ n 之间做binary serach, 但是就比较慢.
方法3:
巧妙的想法.最大的3^x integer是 3^19. 那么找到这个数, 一定可以被n整除. 一步到位.
```
/*
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.
Hide Company Tags Google
Hide Tags Math
Hide Similar Problems (E) Power of Two
*/
/*
Thoughts:
Use binary serach: pick an item, do 3^x and see if equals to n, < n or >n, then move the number.
*/
class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
int start = 0;
int end = n;
while (start + 1 < end) {
int mid = start + (end - start)/2;
long powerOfThree = (long) Math.pow(3, mid);
if (powerOfThree == n) {
return true;
}
if (powerOfThree < n) {
start = mid;
} else {
end = mid;
}
}
return Math.pow(3, start) == n;
}
}
//Check if n = 3 ^ x;
public class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
if (n == 1) {
return true;
}
if (n % 3 != 0) {
return false;
}
return isPowerOfThree(n / 3);
}
}
// Shorter version
class Solution {
public boolean isPowerOfThree(int n) {
while (n/3>=1){
if (n%3!=0) return false;
n/=3;
}
return n==1;
}
}
/*
Thoughts:
The largest int is 2^31, and the largest 3^x = 3^19.
If n is power of 3, it should 3^19 % n should == 0
*/
class Solution {
public boolean isPowerOfThree(int n) {
return (n > 0 && Math.pow(3, 19) % n == 0);
}
}
```