Watch 10 video solutions for Power of Four, a easy level problem involving Math, Bit Manipulation, Recursion. This walkthrough by Java Brains has 17,988 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 - 1Follow up: Could you solve it without loops/recursion?
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 | 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 |