Power of Four solution and explanation
Google
9 more videos on this problem
Power of Four - Leetcode 342 - PythonNeetCodeIO · 7:47 · 14K views
Power of Four | LeetCode 342 | C++, Java, PythonKnowledge Center · 12:11 · 12K views
Power of Four | 3 Approaches | Maths | With Proof | Bit Magic | Leetcode - 342codestorywithMIK · 16:38 · 6K views
Power of Four - LeetCode #342 | Give me 3 minutes Python, JavaScript, Java, C++CodingNinja · 3:25 · 1K views
342. Power of Four | Leetcode problem of the dayRuntime Error · 8:27 · 779 views
342. Power of Four | Leetcode Daily - PythonLeetcode Daily · 5:05 · 321 views
Power of Four - LeetCode 342 - JavaLeetCodon · 2:31 · 272 views
Leetcode 342: Power of FourAlgorithms Casts · 4:35 · 130 views
Power of Four - Google Interview Questions - LeetCode 342 Solution - C++nexTRIE · 3:59 · 120 views
Power of Four | LeetCode 342 | RecursioncodeTips · 3:44 · 90 views
The problem
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
Approach overview
Problem Overview: Given an integer n, determine whether it can be written as 4^k for some non‑negative integer k. The number must be positive and divisible by 4 repeatedly until it becomes 1.
Approach 1: Iterative Division (O(log n) time, O(1) space)
This approach repeatedly divides the number by 4 until it is no longer divisible. Start by rejecting non‑positive numbers since powers of four are always positive. While n % 4 == 0, divide n by 4. If the final value becomes exactly 1, the number was a power of four; otherwise it was not. The key insight is that every valid value can be reduced through exact divisions by 4: 64 → 16 → 4 → 1. The loop runs at most log4(n) iterations, giving O(log n) time and O(1) space. This approach relies purely on arithmetic and is easy to reason about during interviews. It fits naturally with problems involving math properties and integer factorization.
Approach 2: Logarithmic Check (O(1) time, O(1) space)
A number is a power of four if log4(n) is an integer. Using logarithm properties, compute log(n) / log(4) and verify that the result is an integer (or extremely close due to floating‑point precision). If the computed value equals its integer cast, n is a power of four. The algorithm performs only constant‑time mathematical operations, giving O(1) time and O(1) space. The catch is floating‑point precision: values like 64 may produce 2.999999 depending on the language. Most implementations handle this with rounding or epsilon comparisons. This method appears frequently in problems focused on numerical properties and math reasoning, though interviewers may also expect alternatives using bit manipulation or recursive decomposition.
Recommended for interviews: The iterative division approach is the safest answer. It is deterministic, avoids floating‑point precision issues, and clearly demonstrates the core mathematical property of powers of four. Mentioning the logarithmic check shows awareness of mathematical shortcuts, but most interviewers prefer the division approach because it is simple, reliable, and easy to implement under pressure.
Approach 1: Iterative Division
This approach involves successively dividing the number n by 4 to check if it results in 1. If n is a power of four, repeatedly dividing it by 4 should eventually reduce it to 1 with no remainder.
def is_power_of_four(n):
if n <= 0:
return False
while n % 4 == 0:
n //= 4
return n == 1public class Solution {
public boolean isPowerOfFour(int n) {
if (n <= 0) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
}#include <iostream>
bool isPowerOfFour(int n) {
if (n <= 0) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}function isPowerOfFour(n) {
if (n <= 0) return false;
while (n % 4 === 0) {
n /= 4;
}
return n === 1;
}#include <stdbool.h>
bool isPowerOfFour(int n) {
if (n <= 0) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}public class Solution {
public bool IsPowerOfFour(int n) {
if (n <= 0) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
}In Python, the algorithm uses a simple while loop to divide n by 4 until n becomes 1, ensuring it is a power of four.
Time Complexity: O(log4 n).
Space Complexity: O(1).
Approach 2: Logarithmic Check
This approach harnesses logarithms to determine if a number is a power of four. For a number n to be a power of four, the logarithm base 4 of n should be an integer. Utilizing the change of base formula, this can be checked without directly using base 4 logarithm functions.
import math
def is_power_of_four(n):
if n <= 0:
return False
log_val = math.log10(n) / math.log10(4)
return log_val == int(log_val)public class Solution {
public boolean isPowerOfFour(int n) {
if (n <= 0) return false;
double log_val = Math.log10(n) / Math.log10(4);
return Math.floor(log_val) == log_val;
}
}#include <iostream>
#include <cmath>
bool isPowerOfFour(int n) {
if (n <= 0) return false;
double log_val = log10(n) / log10(4);
return floor(log_val) == log_val;
}function isPowerOfFour(n) {
if (n <= 0) return false;
const log_val = Math.log10(n) / Math.log10(4);
return Math.floor(log_val) === log_val;
}#include <stdbool.h>
#include <math.h>
bool isPowerOfFour(int n) {
if (n <= 0) return false;
double log_val = log10(n) / log10(4);
return floor(log_val) == log_val;
}using System;
public class Solution {
public bool IsPowerOfFour(int n) {
if (n <= 0) return false;
double log_val = Math.Log10(n) / Math.Log10(4);
return Math.Floor(log_val) == log_val;
}
}Python's math library aids in checking if a number is a power of four by calculating log4(n) and ensuring it's an integer.
Time Complexity: O(1).
Space Complexity: O(1).
Approach 3: Bit Manipulation
If a number is a power of 4, then it must be greater than 0. Suppose this number is 4^x, which is 2^{2x}. Therefore, its binary representation has only one 1, and this 1 appears at an even position.
First, we check if the number is greater than 0. Then, we verify if the number is 2^{2x} by checking if the bitwise AND of n and n-1 is 0. Finally, we check if the 1 appears at an even position by verifying if the bitwise AND of n and 0xAAAAAAAA is 0. If all three conditions are met, then the number is a power of 4.
The time complexity is O(1), and the space complexity is O(1).
function isPowerOfFour(n: number): boolean {
return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}func isPowerOfFour(n int) bool {
return n > 0 && (n&(n-1)) == 0 && (n&0xaaaaaaaa) == 0
}impl Solution {
pub fn is_power_of_four(n: i32) -> bool {
n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa_u32 as i32) == 0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Division | Time Complexity: O(log4 n). |
| Logarithmic Check | Time Complexity: O(1). |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Division | O(log n) | O(1) | General case; preferred in interviews because it avoids floating‑point precision issues |
| Logarithmic Check | O(1) | O(1) | When using mathematical properties and constant‑time checks; acceptable if floating‑point precision is handled |
Frequently asked questions
Is Power of Four easy or hard?
Power of Four is classified as an Easy problem. The logic mainly involves recognizing mathematical patterns or simple division loops. Despite the difficulty rating, it often appears in interviews to check understanding of number properties.
Power of Four Python/Java solution
In Python or Java, the common solution repeatedly divides the number by 4 while n % 4 == 0. After the loop, check whether n equals 1. This implementation runs in O(log n) time and O(1) space.
How to solve Power of Four in O(1)?
Use the logarithmic property of powers: compute log(n) / log(4) and check if the result is an integer. If the value equals its integer form (within floating‑point tolerance), the number is a power of four. This method performs constant-time calculations, giving O(1) time complexity.
What is the best approach for Power of Four?
The iterative division approach is typically the best choice. Repeatedly divide the number by 4 while it remains divisible, then check if the final value becomes 1. This runs in O(log n) time with O(1) space and avoids floating‑point precision issues that appear in logarithmic solutions.
Is Power of Four asked at Google/Amazon/Meta?
Power of Four appears in coding interviews at major tech companies because it tests understanding of number properties and bit patterns. Variants involving powers of two or bit manipulation are common at companies like Google, Amazon, and Meta.
What data structure is used in Power of Four?
The problem does not require complex data structures. It relies on arithmetic checks or mathematical properties. Some optimized variants use bit manipulation to inspect binary patterns of powers of four.
What is the time complexity of Power of Four?
The iterative division method runs in O(log n) time because the value is divided by 4 each iteration. The logarithmic formula approach runs in O(1) time since it performs only a few mathematical operations. Both use O(1) space.