Solution Explanation: 342. Power of Four

This problem asks whether a given integer n is a power of four (i.e., can be expressed as 4x for some integer x). The most efficient solution leverages bit manipulation.

Core Idea:

A number is a power of four if it meets three conditions:

1. Positive: It must be greater than 0. Powers of four are always positive.

2. Single Bit Set: Its binary representation must have only one bit set to 1 (similar to powers of two). This is checked using the bitwise AND operation (&). If n & (n - 1) is 0, then n has only one bit set. Subtracting 1 from a power of four clears the least significant bit and results in a bitwise AND of 0.

3. Even Position: The single set bit must be in an even position (0-indexed). Powers of four have their single 1 bit at an even position. This is checked using a bitmask 0xaaaaaaaa (which is 10101010... in binary). If n & 0xaaaaaaaa is 0, the single bit is in an odd position. If it's equal to n itself, the bit is in an even position.

Algorithm:

1. Check if n > 0.
2. Check if n & (n - 1) == 0. This verifies that only one bit is set.
3. Check if n & 0xaaaaaaaa == 0. This verifies that the single set bit is in an even position.

Time and Space Complexity:

• Time Complexity: O(1). All operations are bitwise operations which take constant time.
• Space Complexity: O(1). The solution uses only constant extra space.

Code Implementation in Different Languages:

The implementations are strikingly similar across languages because the core logic relies on bitwise operations, which are largely language-agnostic.

Python3:

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

Java:

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

C++:

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

Go:

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

TypeScript:

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

JavaScript:

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
};

All these code snippets implement the same bit manipulation logic efficiently. The only difference lies in the syntax of each programming language.