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); }
近期评论