How to Check If a Number is a Power of Four

Problem statement

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) {
    while (n % 4 == 0 && n > 0) {
        n /= 4;
    }
    return n == 1;
}
int main() {
    cout << isPowerOfFour(16) << endl;
    cout << isPowerOfFour(5) << endl;
    cout << isPowerOfFour(1) << endl;
}

Output:
1
0
1

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 bit1 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) {
    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).

---

Thanks for reading. Get my book "10 Classic Coding Challenges" for FREE: