## Friday, January 8, 2016

### LeetCode 326 - Power of Three

http://www.hrwhisper.me/leetcode-power-of-three/
Given an integer, write a function to determine if it is a power of three.
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.
If we put them in a hash set beforehand, then we can query is power of three in O(1) time. I have seen people write in python like this
Python
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 first
public 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);
}
Python
However, the fastest solution is this
Java
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.
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*");
}
http://www.cnblogs.com/grandyang/p/5138212.html

class Solution {
public:
bool isPowerOfThree(int n) {
return (n > 0 && 1162261467 % n == 0);
}
};

class Solution {
public:
bool isPowerOfThree(int n) {
return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0);
}
};
http://fujiaozhu.me/?p=799
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);
}
https://discuss.leetcode.com/topic/33536/a-summary-of-all-solutions-new-method-included-at-15-30pm-jan-8th
Two trivial solutions first:
#Recursive Solution#
public boolean isPowerOfThree(int n) {
return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
}
#Iterative Solution#
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; }

1 -> 0001
2 -> 0010
4 -> 0100
8 -> 1000

public boolean isPowerOfTwo(int n){ int count =0; while (n >0){ count += (n&(0x01)); n >>=1; } return count ==1; }

1 -> 0001
3 -> 0011
9 -> 1001
27 -> 11011

• 问题的本质或者说算法的求解不应该局限于计算机固有的属性，它是游离于计算机体系之外的，只是我们在实际编写代码时，需要考虑计算机体系知识而已。
• 分析问题一定要抓住关键点，power of Two只是一般模式中的一个特例而已，如果单纯的为这个特例设计算法，那么每当遇到新的问题时，往往苦恼不堪，因为并没有抽象出通解。

i=0len(s)1s[i]2i

i=0len(s)1s[i]3i

1 -> 000_001
3 -> 000_010
9 -> 000_100
27 -> 001_000
public boolean isPowerOfThree(int n) { return Integer.toString(n, 3).matches("^10*\$"); }

i=log3(n)=logb(n)logb(3)
public boolean isPowerOfThree(int n) { return (Math.log10(n) / Math.log10(3)) % 1 == 0; }

return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
1

1