342. Power of Four

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<1) return false;
        while(n%4==0) n>>=2;
        return n==1;
    }
};

option 2

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isPowerOfFour(int n) {
        if(n<1) return false;
        if((n&(n-1))!=0) return false;
        return (n&0x55555555) ==n;
    }
};

option 3 - 換底公式

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return (n>0 && int(log10(n)/log10(4))-log10(n)/log10(4)==0 );
    }
};

analysis

  • time complexity O(1)
  • space complexity O(1)