http://www.hrwhisper.me/leetcode-power-of-three/
X.
http://fujiaozhu.me/?p=799
https://discuss.leetcode.com/topic/36150/1-line-java-solution-without-loop-recursion
http://blog.csdn.net/u014688145/article/details/53417543
public boolean isPowerOfTwo(int n){
int count =0;
while (n >0){
count += (n&(0x01));
n >>=1;
}
return count ==1;
}
∑i=0len(s)−1s[i]∗2i
由此power of Three，我们就能想着是否只需要把十进制的power of Three映射到三进制上去即可，然后在三进制的表示域中找出它的规律，并求解答案：
∑i=0len(s)−1s[i]∗3i
得到：
i=log3(n)=logb(n)logb(3)
public boolean isPowerOfThree(int n) {
return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}
判断i 是否为整数即可。这是最直接了当的解法，俗称最终解，计算机一步得到结果。
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?
Could you do it without using any loop / recursion?
bool isPowerOfThree(int n) {
if(n <= 0) return false;
while(n > 1){
if(n %3 != 0) return false;
n/=3;
}
return true;
}
bool isPowerOfThree(int n) {
if (n <= 0) return false;
if (n == 1) return true;
return n % 3 == 0 && isPowerOfThree(n / 3);
}
bool isPowerOfThree(int n) {
return n <= 0 ? false : n == pow(3, round(log(n) / log(3)));
}
http://algobox.org/power-of-three/
A trivial loop / recursion solution is to divide the number by 3 and look at the remainder again and again.
Another idea is based on logarithm rules and float numbers which i don’t like very much. After all the log function it self may actually implemented using loop / recursion.
Since the 32 bit signed integer has at most 20 numbers, here is a list.
1
3
9
27
81
243
729
2187
6561
19683
59049
177147
531441
1594323
4782969
14348907
43046721
129140163
387420489
1162261467
If we put them in a hash set beforehand, then we can query is power of three in
Python
O(1) time. I have seen people write in python like thisPython
Although it seems not using any loop, the
in operation for list in python takes linear time, which indicating a loop underneath. We can use a set instead and put it into a class variable so we can share between calls.Cheating Method
This is not really a good idea in general. But for such kind of
power questions, if we need to check many times, it might be a good idea to store the desired powers into an array firstpublic boolean isPowerOfThree(int n) {
HashSet<Integer> set = new HashSet<>(Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467));
return set.contains(n);
}
However, the fastest solution is this
Java
1
2
3
4
5
|
public class Solution {
boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
|
This works because 3 is a prime number. A 32 bit positive integer is a power of 3 is equivalent to it is a factor of 3^19 = 1162261467.
This doesn’t work for composite number like 4 or 6.
X.
Radix-3 original post
The idea is to convert the original number into radix-3 format and check if it is of format
10* where 0* means k zeros with k>=0.public boolean isPowerOfThree(int n) {
return Integer.toString(n, 3).matches("10*");
}
题目中的Follow up让我们不用循环，那么有一个投机取巧的方法，由于输入是int，正数范围是0-231，在此范围中允许的最大的3的次方数为319=1162261467，那么我们只要看这个数能否被n整除即可，参见代码如下：
解法二：
class Solution { public: bool isPowerOfThree(int n) { return (n > 0 && 1162261467 % n == 0); } };
最后还有一种巧妙的方法，利用对数的换底公式来做，高中学过的换地公式为logab = logcb / logca，那么如果n是3的倍数，则log3n一定是整数，我们利用换底公式可以写为log3n = log10n / log103，注意这里一定要用10为底数，不能用自然数或者2为底数，否则当n=243时会出错，原因请看这个帖子。现在问题就变成了判断log10n / log103是否为整数，在c++中判断数字a是否为整数，我们可以用 a - int(a) == 0 来判断，参见代码如下：
解法三：
class Solution { public: bool isPowerOfThree(int n) { return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0); } };
bool isPowerOfThree(int n) {
if(n == 0) return false;
else return log10(n)/log10(3) - (int)(log10(n)/log10(3)) < 1e-15;
}
https://discuss.leetcode.com/topic/36150/1-line-java-solution-without-loop-recursion
public boolean isPowerOfThree(int n) {
// 1162261467 is 3^19, 3^20 is bigger than int
return ( n>0 && 1162261467%n==0);
}
Two trivial solutions first:
#Recursive Solution#
#Recursive Solution#
public boolean isPowerOfThree(int n) {
return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
}
#Iterative Solution#
update following Stefan's answer below:
public boolean isPowerOfThree(int n) {
if(n>1)
while(n%3==0) n /= 3;
return n==1;
}http://blog.csdn.net/u014688145/article/details/53417543
public boolean isPowerOfK(int n,int k) {
if (n < 1) {
return false;
}
while (n % k == 0) {
n /= k;
}
return n == 1;
}
其中231.Power of Three可以利用二进制进行求解。在对问题没有思路的时候，我们可以heuristic，很自然的想法我们把十进制的数表示成二进制，例如：
1 -> 0001
2 -> 0010
4 -> 0100
8 -> 1000
由此，我们可以简单猜测它power of two，就是在二进制中，出现其中1位是1的情况，其他均为0。有了这猜测，我们只需要从数学上论证它是正确的即可，这里就不再论证了，答案显而易见。
那么对于236题，同样适用嘛？吼吼，咱们继续heuristic下，例如
1 -> 0001
3 -> 0011
9 -> 1001
27 -> 11011
这规律不太对啊，嗯，在二进制中你着实找不到关于power of Three的一般规律。由此，上述这算法并非是通用的。那应该怎么办呢？power of Two和power of Three真的没有一点联系嘛？
我们换个维度考虑问题，所给的数都是十进制的数，而算法2.是把十进制的数映射到了二进制上，因为我们求的是power of Two,那么我们就必须映射到二进制上去嘛？为什么我们会自然而然的把十进制映射到二进制上去，至少我在得知这种解法时，脑中出现的第一反应是计算机是天然的用二进制来表达任何东西的。然而思维的局限性由此产生，想着同样的power of Three就一定要映射到二进制去解决嘛？由此，我得出两个结论：
- 问题的本质或者说算法的求解不应该局限于计算机固有的属性，它是游离于计算机体系之外的，只是我们在实际编写代码时，需要考虑计算机体系知识而已。
- 分析问题一定要抓住关键点，power of Two只是一般模式中的一个特例而已，如果单纯的为这个特例设计算法，那么每当遇到新的问题时，往往苦恼不堪，因为并没有抽象出通解。
回到上述问题，原本并非想着要写出power of Two 十进制到二进制的映射关系，但为了分析问题本质，也必须写一下
考虑power of Ten.你会发现，这个问题很容易解，因为在1，10，100，1000，…..，你只需要统计1出现的个数为1，且其它位都属于0即可。power of Two，我们是把数映射到了二进制表示法，同样地有：
由此power of Three，我们就能想着是否只需要把十进制的power of Three映射到三进制上去即可，然后在三进制的表示域中找出它的规律，并求解答案：
得到：
public boolean isPowerOfThree(int n) { return Integer.toString(n, 3).matches("^10*$"); }1 -> 000_001
3 -> 000_010
9 -> 000_100
27 -> 001_000
主要内容结束了，作为程序员，本着精益求精的精神，把leetCode中介绍的其他算法补充完整。
数学方法：n=3i
判断
但这是有问题的，因为在log10(n)/log10(3) 中，计算机求得的实际解可能为5.0000001 or 4.9999999，所以我们还是用误差来优化该算法吧。
- 1
- 1
至于leetCode官方提供的最后一种方法，暂时还未研究，等有时间再补充吧。
