Vansh Aggarwal

Posted on Apr 9

LeetCode Solution: 326. Power of Three

#leetcode #dsa #programming #tutorial

Cracking the Code: Is It a Power of Three? (LeetCode 326 Deep Dive!) 🤯

Hey there, future coding legends! 👋 Vansh2710 here, ready to tackle another fun LeetCode challenge that might seem simple on the surface but has some neat tricks up its sleeve. Today, we're diving into Problem 326: Power of Three.

This problem is a fantastic way to practice handling edge cases, understanding numerical properties, and even thinking about optimization. Let's get started!

The Problem: What Exactly Are We Looking For? 🤔

We're given an integer n. Our task is to determine if n is a "power of three."

What does "power of three" mean?
It means n can be expressed as 3 raised to some integer exponent x (i.e., n == 3^x).

Let's look at the examples:

Example 1: n = 27
- Is 27 a power of three? Yes! 27 = 3 * 3 * 3 = 3^3. So, we should return true.
Example 2: n = 0
- Is 0 a power of three? No. There's no exponent x for which 3^x equals 0. 3^0 = 1, 3^1 = 3, 3^-1 = 1/3, etc. So, we should return false.
Example 3: n = -1
- Is -1 a power of three? No. Powers of positive numbers (like 3) are always positive. So, we should return false.

Key Constraints:
n will be between -2^31 and 2^31 - 1. This is the typical range for a 32-bit signed integer.

The "Aha!" Moment: How Do We Spot a Power of Three? ✨

Imagine you have a number, say 81. How would you manually check if it's a power of three?

You'd probably do something like this:

Is 81 divisible by 3? Yes, 81 / 3 = 27.
Is 27 divisible by 3? Yes, 27 / 3 = 9.
Is 9 divisible by 3? Yes, 9 / 3 = 3.
Is 3 divisible by 3? Yes, 3 / 3 = 1.
We reached 1! This means 81 is indeed a power of three (3^4).

What if we had 28?

Is 28 divisible by 3? No! 28 % 3 = 1. Since we can't divide it evenly by 3 and reach 1, 28 is not a power of three.

This repeated division gives us a strong hint! However, instead of repeatedly dividing, we can also multiply powers of three and see if we hit n. This is the intuition behind the provided solution. We'll start with 1 (which is 3^0) and keep multiplying by 3, checking if we ever reach n.

Step-by-Step Approach 🚀

Let's break down the strategy used in the solution:

Handle Non-Positive Numbers:
- As seen in Example 2 (n=0) and Example 3 (n=-1), any number less than or equal to 0 cannot be a power of three. So, our very first check should be: if (n <= 0) return false;.
Handle the Base Case (n = 1):
- 1 is 3^0. It's a power of three. So, if (n == 1) return true;. This is an important edge case to handle explicitly to avoid issues in the multiplication loop.
Iterative Multiplication:
- We need a variable, let's call it res (for "result"), to store increasing powers of three. Initialize res = 1 (since 3^0 = 1).
- Now, we'll start a loop. In each iteration, we multiply res by 3.
- After each multiplication, we check if res is equal to n. If it is, n is a power of three, and we can immediately return true.
Why long long for res and a loop for 30 iterations?
- The maximum int value is 2^31 - 1 (approx 2 * 10^9).
- The largest power of three that fits in a positive int is 3^19 = 1,162,261,467.
- 3^20 would already exceed 2^31 - 1.
- To avoid potential overflow issues if n is large (and res might temporarily exceed int max before matching n), it's safer to use long long for res. This ensures res can hold values beyond the int range if needed.
- A loop running 30 times is sufficient because 3^19 is the largest relevant power. We don't need to go much further, and 3^30 would certainly exceed long long max if we were to keep calculating without checking res > n (which isn't strictly necessary here because we check n == res and n is an int). The 30 iterations are a safe upper bound.
No Match Found:
- If the loop finishes without n ever matching res, it means n is not a power of three. We then return false.

The Code 🧑‍💻

Here's the complete C++ solution, based on the structure we discussed:

class Solution {
public:
    bool isPowerOfThree(int n) {
        // Step 1: Handle non-positive numbers
        if (n <= 0) {
            return false;
        }

        // Step 2: Handle the base case n = 1 (3^0)
        if (n == 1) {
            return true;
        }

        // Step 3 & 4: Iterative multiplication and check for match
        // Use long long for 'res' to safely store larger powers of three
        // before comparison, preventing potential overflow issues if n is large.
        long long res = 1; 
        for (int i = 0; i < 30; i++) { // 3^19 is largest power fitting in int, 30 iterations is safe
            res = res * 3; // Calculate the next power of three

            // If current power of three matches n, we found our answer!
            if (n == res) {
                return true;
            }

            // Optimization: If 'res' becomes larger than 'n', 
            // 'n' cannot be a power of three because powers of three only grow.
            // This also helps prevent 'res' from overflowing if n is not a power of 3.
            if (res > n) { 
                return false;
            }
        }

        // Step 5: If loop completes without a match, n is not a power of three
        return false;
    }
};

Time & Space Complexity Analysis ⏱️📏

Time Complexity: O(1)
- Why O(1)? The loop runs a fixed maximum number of times (30 iterations). It does not depend on the input n in a way that scales with n (e.g., n itself is not the loop bound). Performing a fixed number of operations means constant time complexity.
Space Complexity: O(1)
- We use a few variables (n, res, i) which take up a constant amount of memory regardless of the input value n.

Key Takeaways ✨

Edge Cases are Crucial: Always consider 0, negative numbers, and the smallest positive case (1 for powers of three).
Iterative Solutions: For problems involving powers, repeated multiplication or division is a very common and effective pattern.
Preventing Overflow: Be mindful of integer limits. Using long long for intermediate calculations when dealing with potentially large numbers (like res * 3) can save you from subtle bugs.
Constant Time is Awesome: When you can solve a problem in O(1) time, you've done a great job!

This problem also has a fascinating "Follow up" question: "Could you solve it without loops/recursion?" This hints at mathematical properties (like using log functions) or leveraging the fact that the largest power of 3 that fits in an int is a known constant. We'll leave that as a thought exercise for another day! 😉

Hope this breakdown helped you understand LeetCode 326 better! Happy coding!

Authored by Vansh2710. Published on 2026-04-09 23:43:07.

DEV Community