#326

Easy

LeetCode Problem Workspace

Power of Three

Determine if a given integer is a power of three using math and recursion techniques.

Problem Statement

Given an integer n, return true if it is a power of three. Otherwise, return false. A number is a power of three if there exists an integer x such that n equals 3 raised to the power of x.

For example, 27 is a power of three because 27 equals 3 cubed. However, numbers like 0 or -1 cannot be powers of three, as they do not fit this formula. The solution should efficiently check whether a number meets this condition.

Examples

Example 1

Input: n = 27

Output: true

27 = 33

Example 2

Input: n = 0

Output: false

There is no x where 3x = 0.

Example 3

Input: n = -1

Output: false

There is no x where 3x = (-1).

Constraints

-231 <= n <= 231 - 1

Solution Approach

Mathematical Approach

Use logarithms to check if a number is a power of three. Taking the logarithm of n base 3 will return an integer if n is a power of three. However, since logarithmic calculations might involve floating-point precision issues, an alternative check can be using modulo arithmetic.

Recursive Approach

A recursive solution checks if n is divisible by 3. If n equals 1, it’s a power of three. If n is divisible by 3, divide n by 3 and recurse. If any division does not leave an integer, return false.

Iterative Approach

An iterative approach involves continuously dividing the number by 3 until it is less than or equal to 1. If at any point n is not divisible by 3, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. The logarithmic method operates in constant time, O(1), while the recursive and iterative approaches both have a time complexity of O(log n), as the number is repeatedly divided by 3. The space complexity is O(1) for all approaches, as no extra space is used apart from the input variable.

What Interviewers Usually Probe

Evaluate the candidate's understanding of recursion and iteration.
Check if the candidate can efficiently apply math concepts to solve the problem.
Observe how the candidate handles edge cases like negative numbers and 0.

Common Pitfalls or Variants

Common pitfalls

Not handling negative numbers or zero correctly, which can lead to incorrect answers.
Overcomplicating the solution with unnecessary computations when a simpler method exists.
Failing to optimize for large values of n or introducing unnecessary space complexity.

Follow-up variants

Check if n is a power of two instead of three.
Check if n is a power of an arbitrary integer (other than 3).
Implement the solution in a language with different recursion limits.

FAQ

What is the best approach to solve the Power of Three problem?

The most efficient approach is to use logarithms, but iterative or recursive methods are also valid solutions depending on interview constraints.

How do I handle edge cases in the Power of Three problem?

Ensure that you account for negative numbers, zero, and other non-positive values, which cannot be powers of three.

What is the time complexity of the Power of Three problem?

The time complexity is O(log n) for both recursive and iterative approaches, while the logarithmic method can achieve O(1) time complexity.

Can I use recursion to solve this problem?

Yes, recursion is a valid approach. It checks if n is divisible by 3 and continues to divide it until reaching 1 or an invalid state.

What should I focus on during the interview for the Power of Three problem?

Focus on demonstrating a clear understanding of recursion and math principles, and be mindful of handling edge cases efficiently.

terminal

Solution

Solution 1: Trial Division

If $n \gt 2$, we can continuously divide $n$ by $3$. If it's not divisible, it means $n$ is not a power of $3$, otherwise we continue dividing by $3$ until $n$ is less than or equal to $2$. If $n$ equals $1$, it means $n$ is a power of $3$, otherwise it's not a power of $3$.

1

2

3

4

5

6

7

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n > 2:
            if n % 3:
                return False
            n //= 3
        return n == 1

Solution 2: Mathematics

If $n$ is a power of $3$, then the maximum value of $n$ is $3^{19} = 1162261467$. Therefore, we only need to check if $n$ is a divisor of $3^{19}$.

1

2

3

4

5

6

7

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n > 2:
            if n % 3:
                return False
            n //= 3
        return n == 1

Continue Practicing

#342 power of four #273 integer to english words #390 elimination game