[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 nn is a power of 44, it must be n=4x,x0n = 4^x, x \ge 0.

Then:

4x(3+1)x1x1(mod 3)4^x \equiv (3+1)^x \equiv 1^x \equiv 1 \quad (\bmod ~3)

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

Therefore, we can check whether n=4xn = 4^x by whether n1(mod 3)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)O(1).
  • Space Complexity: O(1)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. 😉😃💗