algoadvance

Leetcode 342. 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.

Clarifying Questions

1. Q: What is the range of the integer n? A: The integer n will be within the typical 32-bit signed integer range, i.e., from -2^31 to 2^31 - 1.

2. Q: Is 1 considered a power of four? A: Yes, 1 is 4^0, so it should return true.

3. Q: How should negative numbers be handled? A: Negative numbers will never be a power of four, so they should return false.

Strategy

To determine if a number is a power of four, we can use the following criteria:

1. The number must be positive.
2. The number must be a power of two (only one bit set in its binary representation).
3. The number minus one must be divisible by 3.

Explanation

• Power of Two Check: In binary, powers of two have exactly one ‘1’ and the rest ‘0’s. For example, 1 is 0001, 2 is 0010, 4 is 0100, etc. To check if a number n is a power of two, the condition (n & (n - 1)) == 0 must hold true.
• Power of Four Check: Power of four numbers have specific positions for the set bit (i.e., 4^0 = 1, 4^1 = 4, 4^2 = 16, etc.). Therefore, if a number n is a power of four, then (n - 1) % 3 == 0 is also true because of properties of power of four in modulus arithmetic.

Code

class Solution {
public:
    bool isPowerOfFour(int n) {
        // Check if n is positive
        if (n <= 0) return false;
        // Check if n is a power of two
        if ((n & (n - 1)) != 0) return false;
        // Check if n - 1 is divisible by 3
        return (n - 1) % 3 == 0;
    }
};

Time Complexity

• Time Complexity: O(1) - All operations are constant-time.
• Space Complexity: O(1) - No additional space is required.

This solution efficiently checks if a number is a power of four using bitwise operations and modulus arithmetic, both of which are very efficient.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?