Power of Three

How it works

The largest power of three within signed 32-bit range is 3^19. Its only positive divisors are powers of three. A positive input is therefore a power of three exactly when it divides this constant.

Steps

1. Reject nonpositive values.
2. Compute 3^19 modulo n.
3. Accept when the remainder is zero.

Complexity

• Time: O(1) for the specified 32-bit bound.
• Space: O(1).

Things to watch for

• This constant depends on the integer range.
• One counts as 3^0.
• Avoid logarithm rounding errors by testing integer divisibility.

class Solution:
  def isPowerOfThree(self, n: int) -> bool:
    return n > 0 and 3**19 % n == 0

class Solution {
 public:
  bool isPowerOfThree(int n) {
    return n > 0 && static_cast<int>(pow(3, 19)) % n == 0;
  }
};