返回

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

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)
Licensed under CC BY-NC-SA 4.0
Built with Hugo
Theme Stack designed by Jimmy