【LeetCode】326. Power of Three(優雅な数学解法)

Question
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?
Solution
This can be generalized for any 【prime】 number n. Lets say we have 2 number m & n.

If m is a power of n then for any number p,
    1.  For all p<=m
    2.  m%p = 0 if and only if p is also a power of n

We can use this concept here also. In this case n=3 and m is largest 32bit signed integer which is power of 3, i.e. 1162261467.

bool isPowerOfThree(int p) {
        return  p>0 && 1162261467%p == 0 ;
}

特に,上記の解法は素数にのみ適用される.
他にもいくつかの解法があります.
3の倍数はintの範囲内で限られているので、表を打ってhash_を使うことができます.mapで検索します.
Another question
231.Power of Two
Given an integer, write a function to determine if it is a power of two.
Solution
解法1:
上の問題と同じように、2のパワーもこの定理を満たしています.

    bool isPowerOfTwo(int n) {
        return (n > 0) && (!(2147483648%n)); //2147483648 = 2^31
    }

解法2:
nのバイナリの観点から,nが2のパワーであれば,nのバイナリ表現には1ビットしかない.
この1位を判断したら?
n&(n−1)が0であるか否かを判断するだけであり、もしそうであれば、nには1ビットしかないことを説明する.

    bool isPowerOfTwo(int n) {
        return n>0 && !(n&(n-1));
    }

この解法はより優れており,ビット演算が速く,バイナリの性質を十分に利用している.