Sponsored
Sponsored
This approach involves successively dividing the number n by 4 to check if it results in 1. If n is a power of four, repeatedly dividing it by 4 should eventually reduce it to 1 with no remainder.
Time Complexity: O(log4 n) due to repeated division.
Space Complexity: O(1) because no additional space is used.
1#include <stdbool.h>
2
3bool isPowerOfFour(int n) {
4 if (n <= 0) return false;
5 while (n % 4 == 0) {
6 n /= 4;
7 }
8 return n == 1;
9}The function checks if the integer n is a power of four by dividing n by 4 as long as it is divisible by 4. If n becomes 1, it means n is a power of four. Otherwise, it is not.
This approach harnesses logarithms to determine if a number is a power of four. For a number n to be a power of four, the logarithm base 4 of n should be an integer. Utilizing the change of base formula, this can be checked without directly using base 4 logarithm functions.
Time Complexity: O(1) as logarithmic operations are constant time.
Space Complexity: O(1).
1#include
The solution calculates log4(n) using log10(n) / log10(4) and checks if it's an integer by comparing against its floored value.