πΉ Problem: Power of Three
Difficulty: #Easy
Tags: #Math #Recursion
π Problem Summary
Check if a given integer n is a power of three β meaning it can be expressed as 3^k for some non-negative integer k.
If yes, return True; otherwise, return False.
π§ My Thought Process
-
Brute Force Idea:
Keep dividingnby 3 until we either:- reach exactly 1 β
True(itβs a power of three), or - get a remainder (
n % 3 != 0) βFalse.
- reach exactly 1 β
-
Optimized Strategy:
This is already efficient because:- Each division by 3 reduces
nby a factor of 3. - The number of steps is
O(logβ n), which is tiny for any integer in range. Alternatively, I could check using maximum power of three in int range and modulus, but the loop is simpler.
- Each division by 3 reduces
Algorithm Used:
Iterative division + modulus check.
βοΈ Code Implementation (Python)
class Solution:
def isPowerOfThree(self, n: int) -> bool:
while n != 1:
if n % 3 != 0 or n == 0:
return False
n //= 3
return True
β±οΈ Time & Space Complexity
- Time: O(logβ n) β repeatedly dividing by 3.
- Space: O(1) β no extra storage.
π§© Key Takeaways
- β Using iterative division is a quick and intuitive way to check powers of a number.
- π‘ An alternative approach is using math.log or precomputing the largest power of three in integer range and checking divisibility.
- π Problems like this also appear for powers of two, powers of four, etc., and the logic is nearly identical.
π 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
- [[231 Power of Two]]
- [[342 Power of Four]]
* [[1780 Check if Number is a Sum of Powers of Three]]
π Progress Tracker
| Metric | Value |
|---|---|
| Day | 58 |
| Total Problems Solved | 414 |
| Confidence Today | π |
| Leetcode Rating | 1572 |
Top comments (0)