動機
像這種看起來很水的題目,有的時候都會也一些出乎意料的解法
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;
}