Given an integer n, return true if it is a power of four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4x.
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
Constraints:
- -231 <= n <= 231 - 1
My Solution
Right off, if the number is negative or 0, we can return false right away because it can never be a power of 4. Then we keep dividing by 4 until it is not divisible by 4, meaning it is not a power of 4, or we reach 1, meaning it is a power of 4.
Time complexity is O(log n) because we keep dividing by 4. Space complexity is O(1) because we only require constant extra space.
class Solution {
public boolean isPowerOfFour(int n) {
if (n <= 0) {
return false;
}
while (n > 1) {
if (n % 4 != 0) {
return false;
}
n /= 4;
}
return true;
}
}