342. Power of Four LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 342. Power of Four LeetCode Solution with the best time and space complexity. The solution to Power of Four problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Power of Four solution in C++
Power of Four solution in Java
Power of Four solution in Python
Additional Resources

342. Power of Four LeetCode Solution image

Problem Statement of Power of Four

Given an integer n, return true if it is a power of four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4x.

Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true

Constraints:

-231 <= n <= 231 – 1

Follow up: Could you solve it without loops/recursion?

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(1)

342. Power of Four LeetCode Solution in C++

class Solution {
 public:
  bool isPowerOfFour(unsigned 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 && popcount(n) == 1 && (n - 1) % 3 == 0;
  }
};
/* code provided by PROGIEZ */

342. Power of Four LeetCode Solution in 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;
  }
}
// code provided by PROGIEZ

342. Power of Four LeetCode Solution in 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 n.bit_count() == 1 and (n - 1) % 3 == 0
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents