Power of Three

Problem

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 == 3x.

Follow up: Could you solve it without loops/recursion?

Constraints

• -231 <= n <= 231 - 1

Solution

The problem Power of Three can be solved by checking if 319 is divisble by the given number. The largest power of three that is within an int range is 319. As 3 is a prime number, 319 is only divisble by 31, 32, ..., 319. Therefore, if 319 is divisble by the given number, it indicates that the number is a power of three.

Implementation

class Solution
{
  public:
    bool isPowerOfThree(int n)
    {
        if (n <= 0)
            return false;

        // pow(3, floor(log(INT_MAX) / log(3))) == 1162261467
        return (1162261467 % n == 0);
    }
};