Power of Three

Difficulty: Easy | Acceptance: 51.00% | Paid: No Topics: Math, Recursion

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer x is a power of three if there exists an integer n such that x == 3ⁿ.

• Examples
• Constraints
• Approach 1: Iterative Division
• Approach 2: Base Conversion
• Approach 3: Mathematics (Logarithms)
• Approach 4: Integer Limit

Examples

Example 1

Input:

n = 27

Output:

true

Explanation: 27 = 3^3

Example 2

Input:

n = 0

Output:

false

Explanation: There is no x where 3^x = 0.

Example 3

Input:

n = -1

Output:

false

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

Constraints

-2³¹ <= n <= 2³¹ - 1

Approach 1: Iterative Division

Intuition We can repeatedly divide the number by 3 as long as it is divisible by 3. If we eventually reach 1, the original number was a power of three.

Steps

• Check if n is less than or equal to 0. If so, return false.
• Use a while loop to check if n is divisible by 3 (n % 3 == 0).
• Inside the loop, divide n by 3.
• After the loop, check if n equals 1.

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

Complexity

• Time: O(log₃ n)
• Space: O(1)
• Notes: Simple and robust, but involves a loop.

Approach 2: Base Conversion

Intuition In base 3 (ternary number system), numbers that are powers of 3 are represented as a 1 followed by zeros (e.g., 1, 10, 100, 1000). We can convert the number to base 3 and check this pattern.

Steps

• Handle edge case where n <= 0.
• Convert n to a string representing its value in base 3.
• Check if the string matches the regular expression ^10*$ (starts with 1, followed by zero or more 0s).

import re

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        # Convert to base 3 string
        base3_str = ""
        temp = n
        while temp > 0:
            base3_str = str(temp % 3) + base3_str
            temp //= 3
        return re.fullmatch("10*", base3_str) is not None

Complexity

• Time: O(log₃ n)
• Space: O(log₃ n)
• Notes: Elegant but uses extra space for the string representation.

Approach 3: Mathematics (Logarithms)

Intuition If n is a power of three, then log₃ n must be an integer. We can calculate this using the change of base formula: log₃ n = log₁₀ n / log₁₀ 3.

Steps

• Check if n <= 0.
• Calculate the logarithm of n base 3.
• Check if the result is an integer by comparing the rounded value to the original value (handling floating point precision errors).

import math

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        # Calculate log base 3
        log_res = math.log10(n) / math.log10(3)
        # Check if it is an integer
        return abs(round(log_res) - log_res) < 1e-10

Complexity

• Time: O(1)
• Space: O(1)
• Notes: Constant time, but relies on floating point arithmetic which can be imprecise for very large integers.

Approach 4: Integer Limit

Intuition Since the input is a 32-bit signed integer, the maximum value is 2³¹ - 1. The largest power of 3 that fits in this range is 3¹⁹ = 1162261467. Any power of 3 must be a divisor of this maximum power.

Steps

• Check if n > 0.
• Check if 1162261467 is divisible by n.

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        # 3^19 = 1162261467 is the largest power of 3 that fits in a 32-bit signed integer
        return n > 0 and 1162261467 % n == 0

Complexity

• Time: O(1)
• Space: O(1)
• Notes: The most optimal solution for integer constraints, avoiding loops and floating point errors.