LeetCode Entry

342. Power of Four

15.08.2025 easy 2025 kotlin rust

Is number power of 4?

342. Power of Four easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1081

Problem TLDR

Is number power of 4? #easy

Intuition

  • count bits, look at trailing zeros count, should be even
  • use a bitmask ...1010101010101
  • use (n-1)%3: n-1 = 4^k -1 = (2^k -1)(2^k + 1), from odd,2^n,odd row, one of the odds is always %3: 123, 345, 789, and so on

Approach

  • also fun regex solution

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


// 16ms
    fun isPowerOfFour(n: Int) =
        Regex("^1(?:00)*$").matches(n.toString(2))



// 4ms
    fun isPowerOfFour(n: Int) =
        (0..15).any { n == 1 shl it*2 }



// 1ms
    fun isPowerOfFour(n: Int) =
       n.countOneBits() == 1 && n and 1431655765 == n



// 1ms
    fun isPowerOfFour(n: Int) =
        n.countOneBits() == 1 && (n-1)%3 == 0



// 0ms
    pub fn is_power_of_four(n: i32) -> bool {
        (0..16).any(|p| n == 1 << p * 2)
    }



// 0ms
    bool isPowerOfFour(int n) {
        return n > 0 && (n & n-1) + (n-1)%3 == 0;
    }



// 0ms
    def isPowerOfFour(self, n: int) -> bool:
        return n in [1<<p*2 for p in range(16)]