Power of Three
EasyPrompt
Given an integer n, return true if it is a power of three. Otherwise, return false.
An integer n is a power of three, if there exists an integer x such that n == 3x.
Example 1:
Input: n = 27
Output: true
Explanation: 27 = 33Example 2:
Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.Example 3:
Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses recursion to repeatedly check if the number can be divided by 3. The logic is broken down into base cases: a number is a power of three if, after being divided by 3 some number of times, it becomes 1. If at any point it's not divisible by 3 (and is not 1), it's not a power of three.
Algorithm
- If
n <= 0, it cannot be a power of three, so returnfalse. - If
n == 1, it is3^0, which is a power of three, so returntrue. - If
nis not divisible by 3 (n % 3 != 0), it cannot be a power of three (unless it's 1, which is already handled), so returnfalse. - If none of the above, the number is a positive multiple of 3. Make a recursive call with
n / 3and return its result.
Walkthrough
The function isPowerOfThree is defined recursively. It first handles the base cases. Any number less than or equal to 0 cannot be a power of three. The number 1 is the base case for a successful path (3^0 = 1). If the current number n is not divisible by 3, it breaks the chain of powers of three, so we return false. Otherwise, the function calls itself with the argument n / 3, continuing the process until a base case is met.
class Solution { public boolean isPowerOfThree(int n) { if (n <= 0) { return false; } if (n == 1) { return true; } if (n % 3 != 0) { return false; } return isPowerOfThree(n / 3); }}Complexity
Time
O(log n) The number of recursive calls is proportional to the logarithm of `n` to the base 3. In each call, we perform constant time operations.
Space
O(log n) Each recursive call adds a new frame to the call stack. The depth of the recursion is the number of times `n` can be divided by 3, which is `log_3(n)`.
Trade-offs
Pros
The code can be seen as an elegant and direct translation of the mathematical definition.
It avoids explicit loop constructs.
Cons
Less space-efficient than the iterative approach due to the recursion call stack.
Can lead to a
StackOverflowErrorfor inputs larger than the standard integer types, although this is not an issue with the given constraints.
This is a straightforward and intuitive approach that uses a loop to repeatedly divide the input number n by 3. If the number is truly a power of three, this process will eventually result in 1. If the loop finishes and the number is not 1, it was not a power of three.
Algorithm
- First, handle the edge case: if
nis not positive (n <= 0), returnfalsesince powers of three are always positive. - Use a
whileloop that continues as long asnis greater than 1 and is divisible by 3. - Inside the loop, update
nby dividing it by 3 (n /= 3). - After the loop terminates, check if the final value of
nis 1. If it is, the original number was a power of three.
Walkthrough
We start by checking if n is a positive number, as powers of three cannot be zero or negative. Then, we enter a while loop. The condition for the loop is n % 3 == 0, meaning it continues as long as n is perfectly divisible by 3. Inside the loop, we perform the division n = n / 3. This effectively strips away factors of 3. If the original n was 3^x, after x iterations, n will become 1. If n had other prime factors, the loop would terminate earlier, leaving n as a number other than 1. Finally, we return the result of the check n == 1.
class Solution { public boolean isPowerOfThree(int n) { if (n <= 0) { return false; } while (n % 3 == 0) { n /= 3; } return n == 1; }}Complexity
Time
O(log n) The number of divisions performed in the `while` loop is `log_3(n)`. For each iteration, the operations are constant time.
Space
O(1) This approach uses only a fixed number of variables, so the space required is constant.
Trade-offs
Pros
Easy to understand and implement.
Very efficient in terms of space complexity.
Cons
Uses a loop, which the follow-up question asks to avoid.
Slower than constant-time mathematical or pre-computation approaches.
This approach leverages a mathematical property. If an integer n is a power of three, it can be expressed as n = 3^x for some integer x. By taking the logarithm of both sides, we get log(n) = x * log(3), which means x = log(n) / log(3). The problem then reduces to checking if this calculated x is an integer.
Algorithm
- Handle the edge case: if
n <= 0, returnfalsebecause the logarithm is not defined for non-positive numbers. - Calculate
x = log(n) / log(3). We can use any logarithm base, such as base 10 or the natural logarithm. - Check if the resulting
xis an integer. Due to potential floating-point inaccuracies, it's safer to check ifxis very close to its rounded value rather than using a simple modulo check likex % 1 == 0.
Walkthrough
This method provides a solution without loops or recursion, as requested by the follow-up. First, we ensure n is positive. Then, we compute the value of the exponent x using the change of base formula for logarithms: x = log_b(n) = log_k(n) / log_k(3). Java's Math.log10 or Math.log can be used. The crucial part is to verify if the result is an integer. A naive check result % 1 == 0 is unreliable due to floating-point representation errors. A more robust method is to check if the absolute difference between the result and its nearest integer (Math.round(result)) is smaller than a tiny tolerance value (epsilon, e.g., 1e-10).
class Solution { public boolean isPowerOfThree(int n) { if (n <= 0) { return false; } double logResult = Math.log10(n) / Math.log10(3); // Check if the result is very close to an integer. return Math.abs(logResult - Math.round(logResult)) < 1e-10; }}Complexity
Time
O(1) The `Math.log10` and other arithmetic operations are typically considered constant time for fixed-size numeric types.
Space
O(1) No extra space that scales with the input size is required.
Trade-offs
Pros
Provides a constant-time solution.
Satisfies the follow-up requirement of not using loops or recursion.
Cons
Relies on floating-point arithmetic, which can introduce precision errors. A simple check like
x % 1 == 0might fail for certain inputs (e.g.,log10(243)/log10(3)might evaluate to4.999...).Requires careful handling of the floating-point comparison to be robust.
This is the most efficient approach and directly answers the follow-up question. It leverages the fact that the input n is a 32-bit signed integer. We can pre-calculate the largest power of three that fits within this integer range. Any other power of three must be a divisor of this largest power.
Algorithm
- First, check if
nis positive. Powers of three are always positive. - The largest power of 3 that fits within a 32-bit signed integer is
3^19, which is1162261467. - If
nis a power of three, it must be a divisor of this largest power of three. - Therefore, the check simplifies to
n > 0 && 1162261467 % n == 0.
Walkthrough
The maximum value for a Java int is 2^31 - 1, which is 2,147,483,647. We can find the largest power of 3 that does not exceed this value:
3^19 = 1,162,261,4673^20 = 3,486,784,401(which is too large) So, the largest power of 3 that can be represented as anintis3^19.
The number 3^19 has only one prime factor: 3. If a number n is a power of three (i.e., n = 3^x for some x), its only prime factor is also 3. This means that if n is a power of three, it must evenly divide 3^19. Conversely, if a positive number n evenly divides 3^19, its prime factors must be a subset of the prime factors of 3^19, meaning its only prime factor can be 3. Thus, n must be a power of three. This leads to a very simple and fast check.
class Solution { public boolean isPowerOfThree(int n) { // 1162261467 is 3^19, the largest power of 3 that fits in a 32-bit signed integer. return n > 0 && 1162261467 % n == 0; }}Complexity
Time
O(1) The solution involves only a few primitive operations (a comparison and a modulo), which take constant time.
Space
O(1) No extra space is used.
Trade-offs
Pros
Extremely fast with O(1) time complexity.
Avoids loops, recursion, and floating-point precision issues.
Very simple and concise code.
Cons
This solution is a 'trick' that is only applicable because of the specific constraint that
nis a 32-bit integer.It is not a general solution for arbitrary-precision numbers (e.g.,
BigInteger).
Solutions
Solution
class Solution {public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }}/** * @param {number} n * @return {boolean} */ var isPowerOfThree = function ( n,) { return n > 0 && 1162261467 % n == 0;};class Solution {public: bool isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }};class Solution : def isPowerOfThree ( self , n : int ) -> bool : return n > 0 and 1162261467 % n == 0Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.