Table of Contents
Problem Statement
We are given an integer and we have to check if the number is power of 4 or not. A number is power of 4 if there exist an integer a such that, num= 4^a.
Example
16
true
5
false
Approach 1 (Brute Force)
An obvious way to check if a number is power of 4 or not is to remove all the fators of 4 by repeatedly dividing the number by 4 untill it is divisible by 4. And check finally if the remaining number is equal to 1 or not. If it is 1 then its obvious that there is no any factor other than 4, hence the number was power of 4. If it is not 1 then the number is not power of 4.
Implementation for Power of Four Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfFour(int n)
{
if (n == 0) return false;
while (n % 4 == 0) n /= 4;
if(n==1) return true;
else return false;
}
int main()
{
int n=16;
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}true
Java Program
import java.util.*;
class Rextester{
public static boolean isPowerOfFour(int n)
{
if (n == 0) return false;
while (n % 4 == 0) n /= 4;
if(n==1) return true;
else return false;
}
public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
true
Complexity Analysis for Power of Four Leetcode Solution
Time Complexity
O(logN) : We are dividing the given number by 4 each time. Therefore in worst case the loop will run logN (base 4) times. Hence we can say time complexity is O(logN).
Space Complexity
O(1) : No extra memory is used.
Approach 2 (Precomputation)
We know there will be very limited numbers in an integer(32-bit) range which is power of 4. How ?
Lets see:
We have been given an integer x, therefore : x <= 2^31-1
So maximum power of 4 in this range will be: log4(2^31-1) = 15
Now we can easily store these 15 numbers by doing precomputation.
Therefore we can now find for every number in constant time whether it is a power of 4 or not.
Implementation for Power of Four Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
set<int> nums;
bool isPowerOfFour(int n)
{
return nums.count(n);
}
int main()
{
int n=15;
int x = 1;
nums.insert(x);
for (int i = 1; i < n + 1; ++i)
{
x = x * 4;
nums.insert(x);
}
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}true
Java Program
import java.util.*;
class Rextester{
static int n = 15;
static List<Integer> nums = new ArrayList<Integer>();
static{
int x = 1;
nums.add(x);
for (int i = 1; i < n + 1; ++i)
{
x = x * 4;
nums.add(x);
}
}
public static boolean isPowerOfFour(int n)
{
return nums.contains(n);
}
public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
true
Complexity Analysis for Power of Four Leetcode Solution
Time Complexity
O(1) : We have all numbers which are power of 4 stored in our program. Hence we can search for a given number and return true or false in constant time.
Space Complexity
O(1) : For 32-bit Integer input only 15 numbers are stored in the memory i.e. constant space or O(1).
Approach 3 (Bit manipulation)
Using bit manipulation we can solve this problem very efficiently.
We know for a number to be power of 4, it needs to be power of 2 also. We have already discussed the condition for a number to be power of 2 in Power of Two Leetcode Solution using bit manipulation.
So let’s first check if number is a power of two: x > 0 and x & (x – 1) == 0.
Now we can analyse that if the number is even power of 2 then it will be power of 4, and if the number is odd power of 2 then it will not be power of 4.
In binary representation this number will contain only single 1-bit at even position (power of 4) or at odd position (not power of 4).
Hence if we do bitwise and of a number(power of 4) with number(101010….10)(base 2) the result will be zero.
We can apply above concept by writing second number in hexadecimal as (aaaaaaaa)(base 16).
Implementation for Power of Four Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfFour(int n)
{
return (n > 0) && ((n & (n-1)) == 0) && ((n & 0xaaaaaaaa) == 0) ;
}
int main()
{
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}true
Java Program
import java.util.*;
class Rextester{
public static boolean isPowerOfFour(int n)
{
return (n > 0) && ((n & (n-1)) == 0) && ((n & 0xaaaaaaaa) == 0) ;
}
public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
true
Complexity Analysis for Power of Four Leetcode Solution
Time Complexity
O(1) : Bitwise and is a constant operation.
Space Complexity
O(1) : Constant space.
Approach 4 (Bit Manipulation + Maths)
We know that if a number is power of 4 then it will be even power of 2. Considering both cases for x=2^a :
a=2k or a=2k+1
If we divide these two numbers by 3 we will get remainder as following :
2^2k mod 3 = 4^k mod 3 = (3+1)^k mod 3 = 1
2^(2k+1) mod 3 = 2×4^k mod 3 = 2×(3+1)^k mod 3 = 2
Hence final condition for a number to be power of 4 should be :
x is power of 2 and x % 3 == 1
Implementation for Power of Four Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfFour(int n)
{
return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}
int main()
{
if(isPowerOfFour(16)) cout<<"true"<<endl;
else cout<<"false"<<endl;
return 0;
}true
Java Program
import java.util.*;
class Rextester{
public static boolean isPowerOfFour(int n)
{
return (n > 0) && ((n & (n-1)) == 0) && ((n % 3) == 1) ;
}
public static void main(String args[])
{
int n=16;
System.out.println(isPowerOfFour(n));
}
}
true
Complexity Analysis for Power of Four Leetcode Solution
Time Complexity
O(1) : Constant time.
Space Complexity
O(1) : Constant space.