LeetCode 0342. 4的幂

【LetMeFly】342.4的幂

力扣题目链接：https://leetcode.cn/problems/power-of-four/

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

 

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

 

提示：

• -231 <= n <= 231 - 1

 

进阶：你能不使用循环或者递归来完成本题吗？

方法一：“消4得1法”

所谓“消4得1法”，就是要在原数不为1的时候，每次判断这个数是否为4的倍数，如果是就让这个数÷4，否则就返回false，直到这个数变成1为止，就返回true

注意，$1=4^0$，而$4$的任何次幂都不会为负数。

• 时间复杂度$O(lo{g}_{4}n)$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n <= 0) {
            return false;
        }
        while (n != 1) {
            if (n % 4) {
                return false;
            }
            n /= 4;
        }
        return true;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127104821