Power of Four

📋

Problem

Imagine you are designing a system that needs to quickly verify if a given number represents a perfect power of four, which is crucial for optimizing memory alignment in hardware.

Given an integer n, determine if it is a power of four. Return true if it is, otherwise return false. Input: integer n. Output: boolean indicating if n is a power of four.

-2^31 <= n <= 2^31 - 1You must solve it without using loops or recursion.

Edge cases: 0 → false (zero is not a power of four)1 → true (4^0 = 1)-4 → false (negative numbers cannot be powers of four)

</>

IDE

def isPowerOfFour(n: int) -> bool:public boolean isPowerOfFour(int n)bool isPowerOfFour(int n)function isPowerOfFour(n)

def isPowerOfFour(n: int) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean isPowerOfFour(int n) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isPowerOfFour(int n) {
    // Write your solution here
    return false;
}

function isPowerOfFour(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: true for 0Missing explicit check for n > 0 before bitwise operations.✅ Add 'if n <= 0: return False' at the start of the function.

Wrong: false for 1Mask or power of two check excludes n=1 incorrectly.✅ Allow n=1 to pass power of two and mask checks or add explicit check for n==1.

Wrong: true for 8 or 2Missing mask 0xAAAAAAAA check to ensure set bit is in odd position.✅ Add condition '(n & 0xAAAAAAAA) == 0' to confirm odd bit position.

Wrong: true for negative numbers like -4No check for positive input before bitwise operations.✅ Add 'if n <= 0: return False' at the start.

Wrong: TLE on large inputUsing iterative division or recursion instead of O(1) bit manipulation.✅ Replace loops/recursion with bitwise checks: 'n > 0 and (n & (n-1)) == 0 and (n & 0xAAAAAAAA) == 0'.

✓

Test Cases

Make sure your code handles zero, one, and negative inputs correctly.

Check that your mask correctly identifies the odd bit position for powers of four.

Optimize your solution to use constant time bitwise operations without loops or recursion.

t1_01basic

Input{"n":16}

Expectedtrue

⏱ Performance - must finish in 2000ms

16 is 4^2, so it is a power of four.

💡 Recall that powers of four have exactly one bit set and that bit is in an odd position.

💡 Check if n is positive, a power of two, and the set bit is in an odd position using a mask.

💡 Use (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0 to confirm power of four.

Why it failed: Failed on canonical example: likely not checking the odd bit position mask 0xAAAAAAAA or power of two condition correctly.

✓ Correctly identifies canonical power of four.

t1_02basic

Input{"n":5}

Expectedfalse

⏱ Performance - must finish in 2000ms

5 is not a power of four (binary 101), fails power of two check.

💡 Check if n is a power of two first.

💡 Verify the single set bit is in an odd position using the mask 0xAAAAAAAA.

💡 Return false if n is not positive or fails either condition.

Why it failed: Incorrectly returns true for 5; likely missing power of two check or mask condition.

✓ Correctly rejects non-power of four numbers.

t2_01edge

Input{"n":0}

Expectedfalse

⏱ Performance - must finish in 2000ms

0 is not a power of four.

💡 Remember zero is not a power of any positive number.

💡 Check if n is positive before other conditions.

💡 Return false immediately if n <= 0.

Why it failed: Returns true for 0; must add explicit n > 0 check before bit operations.

✓ Correctly handles zero input.

t2_02edge

Input{"n":1}

Expectedtrue

⏱ Performance - must finish in 2000ms

1 is 4^0, so it is a power of four.

💡 1 is a special case: it is a power of four (4^0).

💡 Check that your code returns true for n=1.

💡 Ensure the mask and power of two checks allow n=1.

Why it failed: Returns false for 1; likely mask or power of two check excludes n=1 incorrectly.

✓ Correctly identifies 1 as power of four.

t2_03edge

Input{"n":-4}

Expectedfalse

⏱ Performance - must finish in 2000ms

Negative numbers cannot be powers of four.

💡 Negative numbers are never powers of four.

💡 Check if n is positive before bitwise checks.

💡 Return false immediately if n <= 0.

Why it failed: Returns true for negative input; missing n > 0 check.

✓ Correctly rejects negative numbers.

t3_01corner

Input{"n":1073741824}

Expectedtrue

⏱ Performance - must finish in 2000ms

1073741824 = 4^15, largest power of four within 32-bit signed int range.

💡 Test the upper boundary power of four within 32-bit int.

💡 Check that your mask and power of two logic works for large inputs.

💡 Use 0xAAAAAAAA mask to verify the set bit is in an odd position.

Why it failed: Fails on large power of four; likely mask or bit position check incorrect for high bits.

✓ Correctly handles large power of four values.

t3_02corner

Input{"n":8}

Expectedfalse

⏱ Performance - must finish in 2000ms

8 is a power of two but not a power of four (bit set in even position).

💡 Check that your code distinguishes power of two from power of four.

💡 Use mask 0xAAAAAAAA to exclude powers of two with set bit in even positions.

💡 Return false if mask condition fails.

Why it failed: Returns true for 8; missing mask check to exclude powers of two not in odd bit positions.

✓ Correctly rejects powers of two that are not powers of four.

t3_03corner

Input{"n":2}

Expectedfalse

⏱ Performance - must finish in 2000ms

2 is a power of two but not a power of four.

💡 Verify that single set bit is in odd position, not just any power of two.

💡 Use mask 0xAAAAAAAA to filter out powers of two with set bit in even positions.

💡 Return false if mask condition fails.

Why it failed: Returns true for 2; missing mask check for odd bit position.

✓ Correctly rejects 2 as not power of four.

t4_01performance

Input{"n":1073741824}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=1073741824 (4^15), test O(1) bit manipulation solution runs within 2s.

💡 Use O(1) bitwise operations instead of loops or recursion.

💡 Check power of two and mask conditions directly.

💡 Avoid iterative division or recursion to pass performance.

Why it failed: TLE due to iterative or recursive approach; must use O(1) bit manipulation.

✓ Solution runs in constant time as expected.

Practice

1. What is the time complexity of generating all permutations of n elements using bitmask DP with iterative tabulation as shown in the code snippet? Assume appending to lists is O(1) amortized.

medium

A. O(n!)

B. O(n * n!)

C. O(n^2 * 2^n)

D. O(2^n * n!)

Solution

1. Step 1: Identify number of states and transitions

   There are 2^n bitmask states. Each state has up to n transitions to add an unused element.

2. Step 2: Calculate total permutations generated

   Total permutations are n!; each permutation is built by adding elements one by one, so total operations ~ n * n!.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time complexity is O(n * n!) due to building all permutations incrementally [OK]

Hint: Generating all permutations requires at least O(n * n!) time [OK]

Common Mistakes:

• Confusing 2^n states with n! permutations
• Ignoring the cost of building each permutation step

2. What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula [i ^ (i >> 1) for i in range(1 << n)]?

medium

A. O(n)

B. O((2^n)!)

C. O(n * 2^n)

D. O(2^n)

Solution

1. Step 1: Analyze the loop iteration count

   The list comprehension iterates over all integers from 0 to 2^n - 1, so 2^n iterations.

2. Step 2: Analyze work per iteration

   Each iteration performs constant time bitwise operations (XOR and right shift), so O(1) per iteration.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is proportional to 2^n, not multiplied by n or factorial [OK]

Hint: Loop runs 2^n times with O(1) work each [OK]

Common Mistakes:

• Confusing n with 2^n and claiming O(n)
• Assuming bitwise operations cost O(n)
• Mistaking factorial complexity from brute force backtracking

3. What is the time complexity of the optimal bitmasking solution that sorts words by length and prunes pairs early when finding the maximum product of word lengths with no common letters?

medium

A. O(n^3) due to triple nested loops over words and characters

B. O(n^2 * k) because each pair requires checking all characters

C. O(n^2 + n*k + n log n) where n is number of words and k is average word length

D. O(n log n) since sorting dominates the runtime

Solution

1. Step 1: Analyze preprocessing steps

   Computing bitmasks takes O(n*k) where k is average word length. Sorting masks by length takes O(n log n).

2. Step 2: Analyze nested loops with pruning

   Nested loops run O(n^2) in worst case, but pruning reduces unnecessary checks. Bitwise AND checks are O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combining all steps yields O(n^2 + n*k + n log n) [OK]

Hint: Bitmask checks are O(1), pruning reduces pairs [OK]

Common Mistakes:

• Assuming O(n^2*k) due to character checks per pair
• Ignoring sorting cost
• Confusing recursion stack space with iterative solution

4. The following code attempts to find the maximum product of word lengths with no common letters. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line 18: Checking bitmask overlap with bitwise AND

B. Line 10: Sorting masks by length in descending order

C. Line 14: Breaking outer loop when max product cannot improve

D. Line 6: Incorrect bit shift by adding 1 to character index

Solution

1. Step 1: Identify bitmask construction

   Line 6 shifts bits by (ord(ch) - ord('a') + 1), which incorrectly shifts by 1 extra, causing wrong bitmask representation.

2. Step 2: Impact of incorrect bitmask

   This causes overlap checks to fail or miss common letters, leading to incorrect max product or missed pruning opportunities.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask must shift by (ord(ch) - ord('a')) exactly [OK]

Hint: Bit shift must match character index exactly [OK]

Common Mistakes:

• Off-by-one bit shifting in bitmask
• Not pruning pairs after sorting
• Incorrect overlap check logic

5. What is the time complexity of the trie-based maximum XOR algorithm for an input array of size n, where each number fits in 32 bits?

medium

A. O(n^2)

B. O(n * log M), where M is the max number value

C. O(n * 32^2)

D. O(n * 32)

Solution

1. Step 1: Identify operations per number

   Each number is inserted into the trie by processing 32 bits, so insertion is O(32) per number.

2. Step 2: Find max XOR per number

   For each number, traversing trie to find max XOR also takes O(32) steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity is O(n * 32) = O(n), since 32 is constant [OK]

Hint: 32 bits fixed, so linear in n [OK]

Common Mistakes:

• Confusing log M with n
• Assuming quadratic due to nested loops
• Counting 32^2 instead of 32