[LeetCode][342. Power of Four] Just One Line Code with Detailed Explanation

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 679 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Just One Line Code with Detailed Explanation of Problem 342. Power of Four.

Math

If \(n\) is a power of \(4\), it must be \(n = 4^x, x \ge 0\).

Then:

\[ 4^x \equiv (3+1)^x \equiv 1^x \equiv 1 \quad (\bmod ~3) \]

If \(n = 2^x\) but \(n \ne 4^x\), it must be \(n = 4^x \times 2\), which means \(n \equiv 2 \quad (\bmod ~3)\).

Therefore, we can check whether \(n = 4^x\) by whether \(n \equiv 1 \quad(\bmod ~3)\).

1
2
3
4
5
class Solution {
    public boolean isPowerOfFour(int n) {
        return  (n & (n - 1)) == 0 && n % 3 == 1;
    }
}

Analysis

  • Time Complexity: \(O(1)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗