Skip to content

342. Power of Four

Description

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 == 4x.

 

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

 

Constraints:

  • -231 <= n <= 231 - 1

 

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

Solutions

Solution 1: Bit Manipulation

If a number is a power of 4, then it must be greater than \(0\). Suppose this number is \(4^x\), which is \(2^{2x}\). Therefore, its binary representation has only one \(1\), and this \(1\) appears at an even position.

First, we check if the number is greater than \(0\). Then, we verify if the number is \(2^{2x}\) by checking if the bitwise AND of \(n\) and \(n-1\) is \(0\). Finally, we check if the \(1\) appears at an even position by verifying if the bitwise AND of \(n\) and \(\textit{0xAAAAAAAA}\) is \(0\). If all three conditions are met, then the number is a power of 4.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

1
2
3
4
5
class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};

1
2
3
func isPowerOfFour(n int) bool {
    return n > 0 && (n&(n-1)) == 0 && (n&0xaaaaaaaa) == 0
}

1
2
3
function isPowerOfFour(n: number): boolean {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}

1
2
3
4
5
6
7
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
};

Comments