Power of Four - Solution & Explanation
Problem Statement
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?
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.
The function checks if the integer n is a power of four by dividing n by 4 as long as it is divisible by 4. If n becomes 1, it means n is a power of four. Otherwise, it is not.
Complexity
Time Complexity: O(log4 n) due to repeated division.
Space Complexity: O(1) because no additional space is used.
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.
The solution calculates log4(n) using log10(n) / log10(4) and checks if it's an integer by comparing against its floored value.
Complexity
Time Complexity: O(1) as logarithmic operations are constant time.
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).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Division | Time Complexity: O(log4 n) due to repeated division. |
| Logarithmic Check | Time Complexity: O(1) as logarithmic operations are constant time. |
| Bit Manipulation | — |
Detailed 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 |
Video Solution
Power of Four - Leetcode 342 - Python • NeetCodeIO • 14,502 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Power of Four easy or hard?
Power of Four Python/Java solution
How to solve Power of Four in O(1)?
What is the best approach for Power of Four?
Is Power of Four asked at Google/Amazon/Meta?
What data structure is used in Power of Four?
What is the time complexity of Power of Four?
Ready to solve this problem?
Practice Power of Four with our built-in code editor and test cases.
Practice on FleetCode