326. Power of Three

Leetcode Math

Given an integer, write a function to determine if it is a power of three.

Example 1:

Input: 27
Output: true

Example 2:

Input: 0
Output: false

Example 3:

Input: 9
Output: true

Example 4:

Input: 45
Output: false

Follow up:

• Could you do it without using any loop / recursion?

分析

最直接的办法，一定就是一直除以3，直到1为止，看它是否等于1。

public boolean isPowerOfThree(int n) {
    if (n < 1) return false;
    while (n % 3 == 0) n /= 3;
    return n == 1;
}

题目还要求不使用任何循环，其实对于任何质数$k$，都有当$n % k = 0$时，$n$是$k$的指数。

public boolean isPowerOfThree(int n) {
    // 1162261467 is 3^19,  3^20 is bigger than int  
    return (n > 0) &&  (1162261467 % n == 0);
}