289. Power of Four
Given an integer n, decide whether it is a power of four — that is, whether some integer k >= 0 exists with n = 4^k. The function receives n and returns true or false.
The powers of four start 1, 4, 16, 64, 256, …. Note that n can be zero or negative, and none of those values qualify.
A loop of divisions settles it easily — the interview follow-up is to answer in O(1) with no loop and no recursion, using the bit pattern of n.
Example 1:
Input: n = 16
Output: true
Explanation: 16 = 4 × 4 = 4^2.
Example 2:
Input: n = 5
Output: false
Explanation: 5 sits between 4^1 = 4 and 4^2 = 16; no exponent produces it.
Example 3:
Input: n = 8
Output: false
Explanation: 8 is a power of two (2^3) but not a power of four — its lone binary 1 sits at an odd position.
Constraints:
- -2³¹ ≤ n ≤ 2³¹ - 1
Hints:
Keep dividing by 4 while it divides evenly. What must remain at the end if n really was a power of four? Handle n <= 0 before the loop.
Every power of four is first a power of two: exactly one binary 1, so n > 0 and (n & (n - 1)) == 0. What separates 4, 16, 64 from 2, 8, 32? Look at *which position* the single 1 occupies — a mask like 0b...01010101 can test it in one AND.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 16
Expected output: true