Power of Four
Easy · Bit Manipulation · Math · Bit Manipulation · Recursion
Problem
Given an integer n, return true if n equals 4^x for some integer x >= 0, and false otherwise.
1 counts as a power of four (4^0). Zero and negative numbers never do. Try to answer without a loop or recursion.
Examples
Input: n = 64 Output: true
64 = 4^3.
Input: n = 32 Output: false
32 = 2^5 is a power of two, but its single set bit is at an odd position (bit 5), so it is not a power of four.
Input: n = 1 Output: true
1 = 4^0.
Constraints
- -2^31 <= n <= 2^31 - 1
Approaches
- Baseline: divide by four — time O(log n), space O(1)
Follow-up
The same pattern answers "is n a power of eight" (one bit at a position divisible by 3, mask 0x49249249) or of any 2^k. For a base that is not a power of two, such as 3, there is no bit trick; one O(1) answer is to check whether the largest power of 3 that fits in 32 bits is divisible by n. The use cases ask which power of four n is, and which numbers are sums of distinct powers of four.
Related problems
Start free on Cariara · Coding problems · System design studio
