Leetcode

Power of Four

  • Time:O(1)
  • Space:O(1)

C++

class Solution {
 public:
  bool isPowerOfFour(int n) {
    // Why (4^n - 1) % 3 == 0?
    // (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are
    // three consecutive numbers; among one of them, there must be a multiple
    // of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.
    // Therefore, 4^n - 1 is a multiple of 3.
    return n > 0 && __builtin_popcountll(n) == 1 && (n - 1) % 3 == 0;
  }
};

JAVA

class Solution {
  public boolean isPowerOfFour(int n) {
    // Why (4^n - 1) % 3 == 0?
    // (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are
    // three consecutive numbers; among one of them, there must be a multiple
    // of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.
    // Therefore, 4^n - 1 is a multiple of 3
    return n > 0 && Integer.bitCount(n) == 1 && (n - 1) % 3 == 0;
  }
}

Python

class Solution:
  def isPowerOfFour(self, n: int) -> bool:
    # Why (4^n - 1) % 3 == 0?
    # (4^n - 1) = (2^n - 1)(2^n + 1) and 2^n - 1, 2^n, 2^n + 1 are
    # three consecutive numbers among one of them, there must be a multiple
    # of 3, and that can't be 2^n, so it must be either 2^n - 1 or 2^n + 1.
    # Therefore, 4^n - 1 is a multiple of 3.
    return n > 0 and bin(n).count('1') == 1 and (n - 1) % 3 == 0