256. Power of Four Gate
A signal gate only opens for amplification factors that are exact powers of four: 1, 4, 16, 64, and so on. Factors such as 2, 8 or 32 (powers of two that are not powers of four), zero and negative values must keep the gate closed.
Given the 32-bit signed integer n, return true if there exists a non-negative integer k with n == 4^k, otherwise return false. For instance 1024 qualifies (4^5) but 2048 does not. Solve it without loops or recursion, in constant time and constant space, by inspecting the bit pattern of n.
Example 1
- Input:
- n = 1024
- Output:
- true
- Explanation:
1024 = 4^5, a single set bit at an even position.
Example 2
- Input:
- n = 2048
- Output:
- false
- Explanation:
2048 = 2^11 is a power of two, but its set bit is at an odd position, so it is not a power of four.
Example 3
- Input:
- n = -16
- Output:
- false
- Explanation:
Negative values are never powers of four.
Constraints
-231 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(1)
- Space
- O(1)