342. Power of Four – Leetcode Solutions

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        # Step 1: Check if the number is positive
        if n <= 0:
            return False
        
        # Step 2: Check if n is a power of two (only one bit set)
        if n & (n - 1) != 0:
            return False
        
        # Step 3: Check if the set bit is in an odd position
        # The bitmask '0x55555555' has 1s in the odd positions for 32 bits:
        # (01010101010101010101010101010101 in binary)
        # This ensures the single set bit is in the correct position for a power of 4.
        if n & 0x55555555 == 0:
            return False
        
        # If all checks pass, n is a power of 4
        return True

class Solution {
public:
    bool isPowerOfFour(int n) {
        // First, check if n is greater than zero.
        // Powers of four must be positive numbers.
        if (n <= 0) return false;

        // Check if n is a power of two using bitwise operation.
        // A power of two has only one bit set in its binary representation.
        // Example: 4 -> 100, 16 -> 10000. Both have only one bit set to 1.
        // This can be verified using the expression: (n & (n - 1)) == 0
        // If this condition is true, n is a power of two.
        if ((n & (n - 1)) != 0) return false;

        // Now, we need to check if n is a power of four and not just any power of two.
        // For powers of four, the only set bit must be in an odd position (1-based index).
        // Example: 4 -> 100 (set bit is at position 3), 16 -> 10000 (set bit is at position 5).
        // We can use the mask 0x55555555, which is a binary pattern where bits in odd positions are set.
        // 0x55555555 in binary: 1010101010101010101010101010101
        // Performing n & 0x55555555 will check if the set bit is in an odd position.
        return (n & 0x55555555) != 0;
    }
};

var isPowerOfFour = function(n) {
    // Step 1: A number must be positive to be a power of four.
    if (n <= 0) {
        return false;
    }

    // Step 2: A power of four number in binary has a single '1' followed by an even number of '0's.
    // So first, check if n is a power of two by using the bitwise AND operation.
    // Power of two numbers have only one '1' in their binary representation.
    // Example: 4 (binary 100) is a power of two.
    // If n & (n - 1) === 0, then n is a power of two.
    if ((n & (n - 1)) !== 0) {
        return false;
    }

    // Step 3: Now we know n is a power of two, but we need to ensure it is specifically a power of four.
    // This can be checked by ensuring that the '1' in the binary representation of n
    // appears at an even position (counting from the right starting at 0).
    // We use the mask 0x55555555, which in binary is 1010101010101010101010101010101.
    // This mask will have '1' at all the positions that a power of 4 number can have its '1' at.
    // If (n & 0x55555555) is true, then n is a power of 4.
    return (n & 0x55555555) !== 0;
};

class Solution {
    public boolean isPowerOfFour(int n) {
        // Check if the number is positive, since powers of four are always positive.
        if (n <= 0) {
            return false;
        }
        
        // Check if n is a power of two by confirming that it has only one bit set in binary.
        // This is done using the expression (n & (n - 1)) == 0.
        // For example, 16 in binary is 10000, and 15 is 01111, so 16 & 15 == 0.
        if ((n & (n - 1)) != 0) {
            return false;
        }

        // If n is a power of two, we now check if it's a power of four.
        // Powers of four have their only set bit at even positions in the binary representation.
        // We use a mask to check if the set bit is in the correct position for powers of four.
        // The mask 0x55555555 in hexadecimal is 1010101010101010101010101010101 in binary,
        // which has bits set only at even positions (starting from the least significant bit).
        return (n & 0x55555555) != 0;
    }
}