Given a number, find whether the given number is a power of four or not ?
This question is given in the today’s leetcode daily challenge. Let’s discuss how to solve it.
Constraint: -2³¹ ≤ n ≤ 2³¹ -1
There can be multiple ways to solve a question. Let’s discuss few ways:
Example:
n = 5 || output: false
n = 16 || output: true
Using Set
This is a straight forward solution. We can add all the powers of 4 till 2³² to the set iteratively.
Then check whether, n is present in that set or not.
If it is present in the set, return true. Else return false.
Bitwise Operations
Intuition:
If we can carefully observe, we can see that, in the binary representation of the powers of 4, there is only one set bit. This set bit lies on the even position from the right side of the binary representation. ( 0-based position)
1 = 00000001 (set bit is at 0th position from the right)
4 = 00000100 (set bit is at 2nd position from the right)
16 = 00010000 (set bit is at 4th position from the right)
Algorithm:
- Count the number of 1’s in the binary representation of n.
- Check if number of 1’s is equals to 1 and is present in the even position, then return true.
- Else return false.
Problem: https://leetcode.com/problems/power-of-four
My profile: https://leetcode.com/patrisrikanth12/
Thanks for reading.
