342. Power of Four
1. Description
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 == $4^x$.
2. Example
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
3. Constraints
- $-2^{31}$ <= n <= $2^{31} - 1$
4. Follow Up
- Could you solve it without loops/recursion?
5. Solutions
My Accepted Solution(Follow Up)
Time complexity: O(1)
Space complexity: O(1)
// i & (i - 1) could replace the most right bit 1 in i with bit 0
class Solution
{
public:
// bool isPowerOfFour(int n)
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1)) == 0 && (num - 1) % 3 == 0;
}
};
5.1 Math - Squr(Follow Up)
Time complexity: O(1)
Space complexity: O(1)
// if a number is pow(4, x), means number = 4^x = (2^2)^x = 2^2x
// so lg(number) is 2x, which is an even number
// so, we could check whether a number's squr is am even number
// but there is no log function at C++
5.2 Math - Check 1Bit(Follow Up)
Time complexity: O(1)
Space complexity: O(1)
// 1 << 0 == 1
// 1 << 1 == 2
// 1 << 2 == 4
// 1 << 3 == 8
// 1 << 4 == 16
// we could see the 1bit of pow(4) locates at the even position
// so, number & 10101010... will get 0
// 1010101010... could be represented by 0xa
class Solution
{
public:
// bool isPowerOfFour(int n)
bool isPowerOfFour(int num)
{
return ((num > 0) && ((num & (num - 1)) == 0) && ((num & 0xaaaaaaaa) == 0));
}
};