My non-loop solution with no relation to the bit length of int


  • 21
    C
    class Solution {
    public:
        bool isPowerOfFour(int num) {
            if (num <= 0) return false;
            if (num & num - 1) return false;
            return num % 3 == 1;
        }
    };
    

    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:

    1. num must be positive
    2. num must be power of 2
    3. num mod 3 must be 1

  • 0

    @cathook (3 + 1) ^ n (n >= 0) has multiple components that all has 3 as one of factors except the trailing 1. That's why all number which is power of four have residual as 1 when they modulo 3.


  • 0
    W

    And as 2^n = (3-1)^n, if n is odd, then we will get 3*m-1, which the modulo is 2


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.