We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Power of Three

Number: 326

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Meta, Goldman Sachs, Amazon

Problem Description

Determine if a given integer n is a power of three. In other words, check whether there exists an integer x such that n equals 3 raised to the power x.

Key Insights

  • The problem is defined in terms of exponents; we need to verify if n can be represented as 3^x.
  • For n <= 0, the answer is always false since powers of three are positive.
  • One clever method for a constant time solution involves using the fact that the maximum power of three that fits in a 32-bit signed integer divides any smaller power of three without a remainder.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

We can use a mathematical trick to verify if n is a power of three.

  1. First, check that n is positive since negative numbers and zero cannot be a power of three.
  2. For the 32-bit integer range, the highest power of three is 3^19 (which equals 1162261467).
  3. If n is a divisor of 1162261467, then it must be a power of three because a power of three will divide a higher power of three exactly.
    This approach uses basic arithmetic and does not involve any loops or recursion, aligning with the follow-up requirement.

Code Solutions

# Function to determine if n is a power of three.

def is_power_of_three(n: int) -> bool:
    # Check if n is positive.
    if n <= 0:
        return False
    # 1162261467 is 3^19, the largest power of three that fits in a 32-bit signed integer.
    max_power_of_three = 1162261467
    # If n is a divisor of 1162261467, it is a power of three.
    return max_power_of_three % n == 0

# Example usage:
print(is_power_of_three(27))  # Expected output: True
print(is_power_of_three(0))   # Expected output: False
print(is_power_of_three(-1))  # Expected output: False
← Back to All Questions