動機

像這種看起來很水的題目,有的時候都會也一些出乎意料的解法

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.

 

Example 1:

Input: n = 27Output: true

Example 2:

Input: n = 0Output: false

Example 3:

Input: n = 9Output: true

Example 4:

Input: n = 45Output: false

 

Constraints:

  • -231 <= n <= 231 - 1

 

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

Sol

先算int溢位之前最大的3的次方,之後就是看能不能整除!!

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

也可以用限制先算

constexpr int MaxPowerOfThree() {
    int n = 3;
    while (n < std::numeric_limits<int>::max() / 3) { 
        n = n * 3;
    }    
    return n;
}

bool isPowerOfThree(int n) {
    constexpr int maxPowerOfThree = MaxPowerOfThree();
    return n > 0 && maxPowerOfThree % n == 0;
}