326. Power of Three
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 42.1%
Problem Breakdown
The problem asks us to determine whether a given integer n is a power of three. In other words, we need to check if there exists an integer x such that n == 3^x. The input is a single integer n, and the output should be a boolean value: true if n is a power of three, and false otherwise.
Inputs:
- An integer
n.
Outputs:
- A boolean value (
trueorfalse).
Implicit Constraints/Edge Cases:
- If
nis less than 1, it cannot be a power of three (since powers of three are positive). - The function should handle the full range of 32-bit signed integers.
- Consider edge cases like
n = 0,n = 1, and very large values.
Intuition
A brute-force approach would involve repeatedly dividing n by 3 until it is no longer divisible, checking if the final result is 1. However, this approach has a time complexity of O(log₃(n)), which is acceptable but not optimal.
The key insight to improve upon this is to leverage mathematical properties. Specifically, we can use the fact that the largest power of three within the range of a 32-bit signed integer is 3^19 = 1162261467. If n is a power of three, it must divide this maximum power of three without leaving a remainder.
Approach
We will use the following approach:
- Check if
nis less than or equal to 0. If so, returnfalse. - Use the modulo operation to check if
1162261467 % n == 0. If true, thennis a power of three; otherwise, it is not.
This approach leverages the largest power of three within the integer range and avoids loops or recursion.
Complexity Analysis
- Time Complexity: O(1) - The modulo operation is a constant-time operation.
- Space Complexity: O(1) - We are using only a fixed amount of extra space.
Solution
def isPowerOfThree(n: int) -> bool:
# Edge case: n must be positive to be a power of three
if n <= 0:
return False
# Check if the largest power of three within 32-bit signed integer range is divisible by n
return 1162261467 % n == 0
Edge Cases Handled
- n = 0: The function returns
falsebecause 0 is not a power of three. - n = 1: The function returns
truebecause 3⁰ = 1. - n < 0: The function returns
falsebecause negative numbers cannot be powers of three. - n > 1162261467: The function returns
falsebecause any number greater than the largest power of three within the integer range cannot be a power of three.