1272. Check if a Number is a Power of Four

Given an integer n, determine whether it is a power of four (n = 4^x for some non-negative integer x). Return true if it is, otherwise false. Every power of four is a power of two whose single set bit sits at an even position.

Input: A JSON object {"n": <integer>} which may be zero or negative.

Output: Return true if n is a power of four, otherwise false.

Examples

Input: {"n":16}
Output: true
Explanation: 16 = 4^2, one set bit at even index 4 -> true.

Input: {"n":8}
Output: false
Explanation: 8 = 2^3, its single bit sits at odd index 3 -> false.

Constraints

• -10^12 <= n <= 10^15

Asked by