πΉ Problem: Power of Four
Difficulty: #Easy
Tags: #Math #BitManipulation
π Problem Summary
We are given an integer n.
We must check whether n is a power of four (i.e., can be written as 4^k for some integer k β₯ 0).
Return True if it is, else False.
π§ My Thought Process
Brute Force Idea:
Keep multiplying4until the value exceedsn, checking if it ever equalsn.-
Optimized Strategy:
- Since powers of 4 are always positive, discard
n β€ 0immediately. - Repeatedly divide
nby4while it's divisible. - If we eventually reach
1, thennis a power of four. - Avoid floating-point math (
log) for precision safety.
- Since powers of 4 are always positive, discard
Algorithm Used:
Iterative Division (a loop dividing by 4).
βοΈ Code Implementation (Python)
class Solution:
def isPowerOfFour(self, n: int) -> bool:
while n != 1:
if (n % 4 != 0) or n == 0:
return False
n //= 4
return True
β±οΈ Time & Space Complexity
-
Time: O(logβ n) β each step divides
nby 4. - Space: O(1) β constant memory.
π§© Key Takeaways
- β Powers of 4 are also powers of 2, but with even exponents in base-2 representation.
-
π‘ Could also solve using bit tricks:
- Check if
nis power of two (n & (n-1) == 0) - AND
(n-1) % 3 == 0to confirm itβs power of 4.
- Check if
π This type of problem is common with "power of X" variations.
π Reflection (Self-Check)
- [x] Could I solve this without help?
- [x] Did I write code from scratch?
- [x] Did I understand why it works?
- [x] Will I be able to recall this in a week?
π Related Problems
π Progress Tracker
| Metric | Value |
|---|---|
| Day | 60 |
| Total Problems Solved | 416 |
| Confidence Today | π |
| Leetcode Rating | 1572 |
Top comments (0)