Power of Four
EasyPrompt
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: trueExample 2:
Input: n = 5
Output: falseExample 3:
Input: n = 1
Output: true
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses a loop to check if the given number n is a power of four. We start with a variable, say powerOfFour, initialized to 1. We repeatedly multiply this variable by 4 in a loop. If powerOfFour becomes equal to n at any point, we've found that n is a power of four. If powerOfFour exceeds n, it means n cannot be a power of four, as we've passed the potential value.
Algorithm
- Handle the edge case: If
nis less than or equal to 0, it cannot be a power of four, so returnfalse. - Initialize a long variable
powerOfFourto 1. We uselongto prevent overflow whenpowerOfFour * 4exceedsInteger.MAX_VALUE. - Start a
whileloop that continues as long aspowerOfFouris less thann. - Inside the loop, update
powerOfFourby multiplying it by 4 (powerOfFour *= 4). - After the loop, check if
powerOfFouris equal ton. If they are equal,nis a power of four. Otherwise, it is not.
Walkthrough
The core idea is to generate powers of four one by one and compare them with the input number n. We start with 4^0 = 1. In each step of a loop, we multiply our current number by 4 to get the next power of four. We stop when our generated number is greater than or equal to the input n. Finally, we check if our number is exactly equal to n.
class Solution { public boolean isPowerOfFour(int n) { if (n <= 0) { return false; } long powerOfFour = 1; while (powerOfFour < n) { powerOfFour *= 4; } return powerOfFour == n; }}Complexity
Time
O(log₄ n). The number of iterations in the loop is proportional to the exponent `x` where `4^x` is close to `n`. This is logarithmic with base 4.
Space
O(1). We only use a few variables to store the state, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Works correctly for all valid integer inputs.
Cons
Less efficient than constant-time solutions.
Does not satisfy the follow-up constraint of solving the problem without loops or recursion.
This approach leverages the mathematical properties of logarithms. If an integer n is a power of four, it can be expressed as n = 4^x for some integer x. By taking the logarithm base 4 of both sides, we get log₄(n) = x. This means that for n to be a power of four, log₄(n) must be an integer. We can use the change of base formula log_b(a) = log_c(a) / log_c(b) to calculate this value and check if it's an integer.
Algorithm
- Handle the edge case: If
nis less than or equal to 0, returnfalseas logarithms are not defined for non-positive numbers. - Calculate
x = log(n) / log(4). This uses the change of base formula for logarithms. - Check if the result
xis an integer. A simple way to do this is to check ifxhas no fractional part, for example, by comparing it to its truncated integer value:x == (int)x. - If
xis an integer,nis a power of four; otherwise, it is not.
Walkthrough
This method directly solves for the exponent x in the equation n = 4^x. Since most programming languages provide a natural logarithm (ln or log) or base-10 logarithm (log10), we can compute log₄(n) as log(n) / log(4). The result of this division will be a floating-point number. If this number is a whole number (i.e., has no fractional part), then n is a perfect power of four.
class Solution { public boolean isPowerOfFour(int n) { if (n <= 0) { return false; } double logValue = Math.log(n) / Math.log(4); // Check if the result is an integer. // Comparing with its floor or ceiling also works. return logValue == (int)logValue; }}Complexity
Time
O(1). The `Math.log()` function is typically implemented in a way that its complexity is considered constant for the purpose of algorithmic analysis.
Space
O(1). No extra space proportional to the input size is used.
Trade-offs
Pros
Solves the problem in constant time.
Satisfies the follow-up requirement of not using loops or recursion.
The code is very concise.
Cons
Relies on floating-point arithmetic, which can introduce precision errors for very large numbers, although it's generally safe for standard integer types.
This is a clever constant-time solution that avoids floating-point math and "magic number" bitmasks. It relies on a combination of bit manipulation and a mathematical property of powers of four. A number n is a power of four if and only if it meets two criteria: it must be a power of two, and among powers of two, it must satisfy a specific condition that can be checked with modulo arithmetic.
Algorithm
- Check for positive number:
n > 0. Powers of four are always positive. - Check for power of two:
(n & (n - 1)) == 0. This bitwise trick efficiently verifies if a number has only one bit set to '1' in its binary representation, which is a necessary condition for being a power of two (and thus for being a power of four). - Check the modulo condition:
n % 3 == 1. This condition distinguishes powers of four from other powers of two. Any power of four (4^x) modulo 3 is 1, while other powers of two (2 * 4^x) modulo 3 are 2. - Combine all three checks. If all are true,
nis a power of four.
Walkthrough
First, we establish that n must be a power of two. This is because 4^x = (2^2)^x = 2^(2x), so any power of four is also a power of two. The check (n & (n - 1)) == 0 (for n > 0) confirms this.
Next, we need to differentiate powers of four (e.g., 1, 4, 16, 64) from other powers of two (e.g., 2, 8, 32). Let's look at their values modulo 3:
- Powers of 4:
4^x = (3+1)^x ≡ 1^x ≡ 1 (mod 3). - Other powers of 2:
2 * 4^x ≡ 2 * 1 ≡ 2 (mod 3).
So, a power of two is a power of four if and only if n % 3 == 1.
class Solution { public boolean isPowerOfFour(int n) { // 1. n > 0: Must be positive. // 2. (n & (n - 1)) == 0: Must be a power of 2. // 3. n % 3 == 1: Differentiates powers of 4 from other powers of 2. return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; }}Complexity
Time
O(1). The solution involves a few bitwise and arithmetic operations, which are all constant time.
Space
O(1). No extra space is used.
Trade-offs
Pros
Extremely efficient O(1) time complexity.
Uses only robust integer arithmetic.
Satisfies the follow-up by avoiding loops/recursion.
Arguably more elegant than using a hardcoded bitmask.
Cons
The mathematical reasoning behind the
n % 3 == 1check might not be immediately obvious to everyone.
This is a highly efficient approach that solves the problem without loops or recursion by directly analyzing the binary representation of the number. A number n is a power of four if and only if it satisfies three conditions:
nmust be positive.nmust be a power of two (i.e., have only one '1' bit in its binary form).- The single '1' bit must be at an even-numbered position (0, 2, 4, ... counting from the right).
Algorithm
- Check for positive number:
n > 0. Powers of four are positive (1, 4, 16, ...). - Check for power of two:
(n & (n - 1)) == 0. This ensures the number's binary representation has exactly one bit set to '1'. - Check for '1' bit position: The set bit for a power of four (
4^x = 2^(2x)) is always at an even-numbered position (0, 2, 4, ...). We can use a bitmask0x55555555(binary0101...0101), which has '1's only at the even positions. Ifnis a power of four, ANDing it with this mask will result innitself, as its single '1' bit will align with a '1' in the mask. - Combine all three checks:
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n;
Walkthrough
The first two conditions (n > 0 and (n & (n - 1)) == 0) establish that n is a power of two. The third condition is the key to filtering for powers of four. Powers of four have their single set bit at positions corresponding to even powers of two (2^0, 2^2, 2^4, etc.).
The bitmask 0x55555555 is a 32-bit integer where the bits at even positions (0, 2, ..., 30) are set to 1, and bits at odd positions are 0. Its binary representation is 01010101010101010101010101010101.
When we perform n & 0x55555555, if the single set bit in n is at an even position, it will be preserved, and the result will be n. If the set bit is at an odd position (meaning n is a power of two but not a power of four), it will be masked out, and the result will be 0.
class Solution { public boolean isPowerOfFour(int n) { // 1. n > 0: Must be positive. // 2. (n & (n - 1)) == 0: Must be a power of 2 (only one bit set). // 3. (n & 0x55555555) == n: The set bit must be at an even position. return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n; }}Complexity
Time
O(1). All operations are single, fast CPU instructions.
Space
O(1). No extra space is used.
Trade-offs
Pros
Extremely fast and efficient with O(1) time complexity.
A classic and widely recognized bit manipulation technique.
Satisfies the follow-up constraint of not using loops or recursion.
Cons
The bitmask
0x55555555can seem like a "magic number" if the underlying logic is not understood.
Solutions
Solution
class Solution {public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0; }}/** * @param {number} n * @return {boolean} */ var isPowerOfFour = function ( n,) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;};class Solution: def isPowerOfFour(self, n: int) -> bool: return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0class Solution {public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.