0%

[Leetcode]342. Power of Four

题目描述

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,看最后是否能整除,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
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) 是否是整数即可,代码如下:

1
2
3
4
5
6
class Solution {
public:
bool isPowerOfFour(int num) {
return (num > 0 && (int(log10(num) / log10(4)) == log10(num) / log10(4)));
}
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1)