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

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)$.

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. 😉😃💗