Power Of Four - Leetcode Solution

Problem Statement:

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16 Output: true

Example 2:

Input: 5 Output: false

Follow-up: Could you solve it without loops/recursion?

Solution:

Approach 1: Using Loop

We can solve this using a loop where we keep on dividing the given number by 4 until we get 1 or a number which is not divisible by 4. If we get 1, return true else return false. Here is the implementation for the same:

class Solution { public boolean isPowerOfFour(int num) { if(num<=0) //base case return false; while(num>1) { if(num%4!=0) return false; num=num/4; } return true; } }

Time Complexity: O(log4n) - because in each iteration we are dividing the number by 4.

Approach 2: Using Logarithms

If we have to check whether a number x is a power of 4 or not, then we can take the log base 4 of x and check if it is an integer or not. If it is an integer, then x is a power of 4. Here is the implementation for the same:

class Solution { public boolean isPowerOfFour(int num) { if(num<=0) //base case return false; double i = Math.log10(num)/Math.log10(4); return (i - (int)i) == 0; //true if i is integer, else false } }

Time Complexity: O(1) - because we are using logarithms.

Approach 3: Without Loops/Recursion

We can solve this in O(1) time complexity without using loops/recursion using bit manipulation. A number that is a power of 4 should have only a single 1 bit and that bit should be in an odd index. Here is the implementation for the same:

class Solution { public boolean isPowerOfFour(int num) { if(num<=0) return false; return (num&(num-1))==0 && (num&0b01010101010101010101010101010101)==num; } }

Explanation:

1. (num&(num-1))==0 - checks if the given number has only a single 1 bit.
2. (num&0b01010101010101010101010101010101)==num - checks if the 1 bit is in an odd index.

Time Complexity: O(1) - because we are using bit manipulation.

Conclusion:

We have seen 3 different approaches to solve the Power Of Four problem on LeetCode. All of them are valid and have their own time complexities and space complexities. We can choose the approach that suits our needs best.

1