Power of Four#
Problem statement#
[1]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
.
Example 1#
Input: n = 16
Output: true
Example 2#
Input: n = 5
Output: false
Example 3#
Input: n = 1
Output: true
Constraints#
-2^31 <= n <= 2^31 - 1
.
Follow up#
Could you solve it without loops/recursion?
Solution 1: Division by four#
Code#
#include <iostream>
using namespace std;
bool isPowerOfFour(int n) {
// perform the divison by 4 repeatedly
while (n % 4 == 0 && n > 0) {
n /= 4;
}
// if n % 4 != 0, then n > 1
return n == 1;
}
int main()
{
cout << isPowerOfFour(16) << endl;
cout << isPowerOfFour(5) << endl;
cout << isPowerOfFour(1) << endl;
}
Output:
1
0
1
This solution repeatedly divides the given number n
by 4 until n
becomes either 1 or a number that is not divisible by 4. If n
becomes 1 after this process, it means that n
was originally a power of 4.
Complexity#
Runtime:
O(logn)
.Extra space:
O(1)
.
Solution 2: Binary representation#
You can write down the binary representation of the powers of four to find the pattern.
1 : 1
4 : 100
16 : 10000
64 : 1000000
256 : 100000000
...
You might notice the patterns are n is a positive integer having only one bit 1
in its binary representation and it is located at the odd positions (starting from the right).
How can you formulate those conditions?
If n
has only one bit 1
in its binary representation 10...0
, then n - 1
has the complete opposite binary representation 01...1
.
You can use the bit operator AND to formulate this condition
n & (n - 1) == 0
Let A
be the number whose binary representation has only bits 1
at all odd positions, then n & A
is never 0
.
In this problem, A < 2^31
. You can chooseA = 0x55555555
, the hexadecimal of 0101 0101 0101 0101 0101 0101 0101 0101
.
Code#
#include <iostream>
using namespace std;
bool isPowerOfFour(int n) {
// the condition of the pattern "n is a positive integer
// having only one bit 1 in its binary representation and
// it is located at the odd positions"
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
int main() {
cout << isPowerOfFour(16) << endl;
cout << isPowerOfFour(5) << endl;
cout << isPowerOfFour(1) << endl;
}
Output:
1
0
1
Complexity#
Runtime:
O(1)
.Extra space:
O(1)
.
Conclusion#
Recognizing the unique properties of powers of four, such as their binary representation, can lead to efficient solutions. Solution 2 leverages bitwise operations to check if a number meets the criteria of being a power of four.
By examining the binary representation and ensuring that the only set bit is located at an odd position, Solution 2 effectively determines whether the number is a power of four in constant time complexity, without the need for division operations.
But in term of readable code, Solution 2 is not easy to understand like Solution 1, where complexity of O(logn)
is not too bad.
Exercise#
Power of Two.[2].