题目描述
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
例子
例子 1
Input: 16 Output: true
例子 2
Input: 5 Output: false
Follow Up
Could you solve it without loops/recursion?
解题思路
方法一
最简单的方法是通过循环,一直除4,看最后是否能整除,代码如下:
class Solution {
public:
bool isPowerOfFour(int num) {
while (num && num > 1) {
num /= 4;
}
return num == 1;
}
};
- 时间复杂度: O(log4n)
- 空间复杂度: O(1)
方法二
这道题还有一个不需要用循环的方法,而是通过换底公式来做:logn(M) = log10(M) / log10(n)
。根据这个公式我们只需要判断 log4(num)
是否是整数即可,代码如下:
class Solution {
public:
bool isPowerOfFour(int num) {
return (num > 0 && (int(log10(num) / log10(4)) == log10(num) / log10(4)));
}
};
- 时间复杂度: O(1)
- 空间复杂度: O(1)