algoadvance

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.

Clarifying Questions

  1. Can n be negative?
    • No, powers of three are positive integers.
  2. What is the range of n?
    • The problem traditionally deals with 32-bit signed integers, so n can range from -2^31 to 2^31 - 1.
  3. What if n is zero?
    • Zero is not a power of three, so the result should be False.

Strategy

  1. Iterative Approach: One way to solve this problem is to iteratively divide the number by 3 and check if we can end up with 1.
    • Start with n.
    • If n is less than or equal to 0, return False (since powers of three are positive).
    • Keep dividing n by 3 as long as it’s divisible by 3.
    • After the loop, if n equals 1, then it is a power of three; otherwise, it is not.
  2. Mathematical Approach: Another more elegant solution leverages the fact that the maximum possible power of three that can fit in a 32-bit signed integer is 3^19 which is 1162261467.
    • Any power of three n must be a divisor of 1162261467 if it lies within the 32-bit integer range.

Code

Let’s start with the iterative approach and then also provide the mathematical approach.

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

    def isPowerOfThreeMathematical(self, n: int) -> bool:
        # 3^19 is 1162261467, which is the largest power of three in signed 32-bit integer range.
        return n > 0 and 1162261467 % n == 0

Time Complexity

  1. Iterative Approach: O(log₃(n)). This is because we keep dividing n by 3 until n becomes 1.
  2. Mathematical Approach: O(1). This is because it only involves a couple of arithmetic operations.

Conclusion

Both approaches effectively determine if a number is a power of three, but the mathematical approach is more efficient due to its constant time complexity.

Try our interview co-pilot at AlgoAdvance.com