Power of Three

• medium
• tagged: math
• similar:

判断一个整数是否是3的k次方. (不用loop/recursion怎么写?)

思路

• 最简单的想法就是不断除以3, 直到余数不大于1. 此时之间判断是否为1.
• 看了discuss看到了牛X解法:
  • 因为int最大为: 0x7FFF_FFFF, 所以找到的最大的3^k一定可以整除这个int! 这样主需要1次运算即可! 牛X.

idea 1

• 即便algs简单如此, 我却写的很复杂, 这里是stefan的写法.
• 代码如下:

public boolean isPowerOfThreeIter(int n) {
    if (n > 1) {
      while (n % 3 == 0) {
        n /= 3;
      }
    }
    return n == 1;
  }

• 自然还有recursion写法. 认真理解递归思想: 即此时的解, 即下一步的解拼起来, 代码如下:

public boolean isPowerOfThreeRec(int n) {
    return n > 0 && (n == 1 || (n % 3 == 0 && isPowerOfThree(n/3)));
  }

idea 2: 牛X的数学方法: 1步!!!

• 看看他是怎么找到最大的3的power, 利用了log性质: $$3^k = n \Rightarrow klog3 = log(n) \Rightarrow k = log(n) / log(3)$$
• 代码如下:

public boolean isPowerOfThree(int n) {
    int maxPowerThree = (int) Math.pow(3, (int)(Math.log(0x7fff_ffff) / Math.log(3)));
    return n > 0 && maxPowerThree % n == 0;
  }