Problem Description
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 == 3^x.
Key Insights
- A power of three can only be a positive integer.
- The only valid values for n that are powers of three are 1, 3, 9, 27, 81, etc.
- The maximum power of three within the 32-bit signed integer range is 3^19, which equals 1162261467.
- A number can be checked for being a power of three by continuously dividing it by 3 until it cannot be divided evenly anymore.
Space and Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Solution
To determine if a number n is a power of three, we can use a mathematical approach. Instead of using loops or recursion, we can leverage the fact that if n is a power of three, then n should be able to be expressed as 3 raised to some integer x. We can check this by ensuring that n is greater than 0, and then verifying if 1162261467 (the largest power of three within the 32-bit signed integer range) is divisible by n. If it is, then n is a power of three.