BM342PowerOfFour

Silu

• 1 Use Bit Manipulation
  • 1.1 自己想的 Failed case again!!: n = 0;
  • 1.2 Bit的另一種判定方法也不錯: 主要思想是確認是power of two之後, 再確認是不是power of 4. 附在後面解法1.2
  • 1.3 Another way: 判斷是power of two以後,EVEN number of trailing zeros 來源https://discuss.leetcode.com/topic/42961/two-1-line-java-solutions
  • 1.4 來源同上,還可以將之變為四進制數再判斷
• Use Math, cannot use the power of two one

解法1.2

https://discuss.leetcode.com/topic/43879/my-non-loop-solution-with-no-relation-to-the-bit-length-of-int

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= ) return false;
        if (num & num - ) return false;
        return num %  == ;
    }
};
           

I observed that 2 * k % 3 = 1 if and only if k is even, that is, 2 * k is a power of 4.

So we can just check whether these three conditions are all true:

num must be positive

num must be power of 2

num mod 3 must be 1

public boolean isPowerOfFour(int num) {
    return (num&(num-))== && num> && (num-)%==;
}
           

解法1.3 1.4

https://discuss.leetcode.com/topic/42961/two-1-line-java-solutions

Solution 1: convert it into radix 4 number, and check if it is in format “1”, “10”, “100”, “1000” … etc.

public class Solution {
    public boolean isPowerOfFour(int num) {
        return Integer.toString(num, ).matches("10*");
    }
}
           

Time is O( log n) due to toString and matches both cost O( log n).

Solution 2: check if its binary has only ONE “1” bit and EVEN number of trailing zeros. Theory is similar to above, but no need of conversion into binary.

public class Solution {
    public boolean isPowerOfFour(int num) {
        return (Integer.bitCount(num) == ) && ((Integer.numberOfTrailingZeros(num) % ) == );
    }
}
           

The time is also O( log n), because bitCount and numberOfTrailingZeros both cost O( log n).