算法细节系列（2）：231.Power of Two && Three

算法细节系列（2）：231.Power of Two && Three

前言

在刷leetCode时，遇到了一系列关于power of Number的问题，刚开始不以为然，以为用简单的递归就能求解，可直到看到power of three官方解时，才发现自己的渺小。它的思维深度和广度着实不是我等小菜能够比拟的，但我还是在其基础上强行解释了一些算法的核心思想。

问题

整理自leetCode 231.Power of Two && 236.Power of Three

Given an integer, write a function to determine if it is a power of two. 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?

常规解题手段：

算法1：

//k在这两题中分别取2和3
public class Solution {
    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。有了这猜测，我们只需要从数学上论证它是正确的即可，这里就不再论证了，答案显而易见。我们给出另一种解法。

算法2：

//只针对2的情况
public class Solution {
    public boolean isPowerOfTwo(int n){
            int count =0;
            while (n >0){
                count += (n&(0x01));
                n >>=1;
            }
            return count ==1;
        }
}

那么对于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，我们是把数映射到了二进制表示法，同样地有：

∑i=0len(s)−1s[i]∗2i

\sum_{i=0}^{len(s)-1}s[i]*2^i 由此power of Three，我们就能想着是否只需要把十进制的power of Three映射到三进制上去即可，然后在三进制的表示域中找出它的规律，并求解答案：

∑i=0len(s)−1s[i]∗3i

\sum_{i=0}^{len(s)-1}s[i]*3^i 得到：

1 -> 000_001 3 -> 000_010 9 -> 000_100 27 -> 001_000

我一直在思考这种解法是如何被发现的，思考甚久，始终不得合理的解释。但我还是强行总结了一波，有兴趣的可以继续往下看，因为以下内容和都属于个人猜想，毫无依据可言，甚至是钻牛角尖的结果。

解释1：是那些博学，对数学敏感的那类人能够直接从大脑中构建出联系，灵感一瞬间闪现，被他们抓住解决了这个问题。

解释2：像我这样的人，没有天才般的大脑，但我们可以根据给定的解法进行反推，看看能否总结出有价值的抽象，即问题的本质。power of Ten，Two，Three，我们能想到什么？

10i,2i,3i,i=1,2,...,n

10^i,2^i,3^i,i =1,2,...,n 我们就拿10i10^i举例说明，它的可能形式有1,10,100,1000,…这是什么东东？我们千万不能把它们想象成数字，一定要用符号去抽象。 1只是代表1的符号，10是“1”和“0”的组合而已。因此我们可以试着把1,10,100,1000,…写成b,ba,baa,baaa,…符合这样的形式即可。

符号？你能想到啥？不够，10i10^i结合符号，还能想到啥？笛卡尔积！啊，什么！为什么是笛卡尔积，好吧，我也不知道为什么。或许学过离散数学的话，可能就有这样的联想吧，大脑就是个神奇的东西，无意之间就能把学到的一些知识联系在一块，从而推导出想要的结论。离散数学中有一章节关于关系的内容，什么是关系我们在这不去探讨，但我们知道一个集合，如：

{a,b,c}

\{a,b,c\} 它的笛卡尔积是什么？

{a,b,c}×{a,b,c}={aa,ab,ac,ba,bb,bc,ca,cb,cc}

\{a,b,c\}\times\{a,b,c\} = \{aa,ab,ac,ba,bb,bc,ca,cb,cc\} 这是二元关系的笛卡尔积，我们研究笛卡尔积的长度，已知集合中的元素个数为3，二元关系的笛卡尔积长度为3×3=93\times3 =9，那么推广到n元关系笛卡尔积的长度则为3n3^n，咦，power of Three，没错n元关系的笛卡尔积就表示power of Three，num = 3n.3^n.当然这是因为集合的元素为3个的情况，集合元素个数为10的情况，则n元笛卡尔积的长度为10n10^n。那为什么是笛卡尔积来代表这个问题的抽象呢？因为刚才我们从10得到了启发，1和0只是符号。那么该问题就由3n3^n转换到集合元素个数为3的符号问题了，也就是从十进制转换到符号问题。

我们需要充分利用笛卡尔积的长度，来找到符号和3n3^n的关系。这又需要费一番周折，可总能找到一些线索逼近答案。我是从计数进制原理得到启发，看下表：

在进制的表示中，符号是存在冗余信息的。上述表格同样存在这种冗余信息，仔细看看我们的计数形式，从0-10对各个元素进行计数。我们可以简单的认为a=0，b=1，c=2，这是一元关系中的表现形式，然而在二元笛卡尔积中，我们认为aa =0，ab =1，ac =2，可直观上来说，a和aa表示不相等才比较合理。但不管如何，由此得，该集合的冗余长度为3，在三元笛卡尔积中，同理，前9个元素在二元笛卡尔积中都得到了表示，所以冗余长度为32=93^2=9，神奇的事情发生了，二元笛卡尔积的冗余度，可以由一元笛卡尔积元素末尾的后一位表示，即ba =3，而三元笛卡尔积的冗余度，可以由该集合元素末尾的后一位表示，即baa = 9。

由上述结论，我们找到了3n3^n和符号之间的关系了，我们只需要通过某种算法把num映射到{a,b,c}\{a,b,c\}的某个n元关系的笛卡尔积上的某个元素，然后判断是否符合ba*的形式。

我想表达什么呢？这不是废话嘛，谁都能看出这种关系来，但试想着如果三进制的进位原理并不符合上表展现的那样，我们还能否简单的把它映射到三进制中去做嘛。如三进制的进位三元素{0,1,2}换成{1,2,3}单独把0当作一个元素，排除在进位原则外。（进位原理，后期再更新）

说了那么多其实这就是十进制转换三进制的问题，因为上表是符合三进制进位原则的。我们把{a,b,c}\{a,b,c\} 映射成{0,1,2}\{0,1,2\}，所有问题迎刃而解。即公式：

∑i=0len(s)−1s[i]∗3i

\sum_{i=0}^{len(s)-1}s[i]*3^i

个人觉得上述，关于该算法的解释有点牵强，但有一点是我从归纳和总结中学到的，对于问题的求解，我们并不一定要在“十进制”领域去考虑，可以换一个相关域，两个域之间存在的联系是我们建立的映射关系的手段，而相关域的理论能够帮助我们解决问题，看透问题的本质以及扩展我们的思维。

• 数一定是数嘛？它只是符号。
• 数就没有其他表现形式了嘛？它一定是最合理的嘛？（符号冗余度为knk^n,k表示进制数，计数进制规则并非是最佳的。历史原因？0元素归并？）

有了上述规则，我们再实现我们的算法3。

算法3：

// power of Three
public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}

主要内容结束了，作为程序员，本着精益求精的精神，把leetCode中介绍的其他算法补充完整。

数学方法：n=3in = 3^i

i=log3(n)=logb(n)logb(3)

i = \log_3(n) = \frac {\log_b(n)}{\log_b(3)} 判断ii是否为整数即可。这是最直接了当的解法，俗称最终解，计算机一步得到结果。

算法4：

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

但这是有问题的，因为在log10(n)/log10(3)log_{10}(n) / log_{10}(3)中，计算机求得的实际解可能为5.0000001 or 4.9999999，所以我们还是用误差来优化该算法吧。

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

至于leetCode官方提供的最后一种方法，暂时还未研究，等有时间再补充吧。

参考文献：

1.https://leetcode.com/articles/power-of-three/