Power of Two

📋

Power of Two

Edge cases:

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: true for 0Missing check for n <= 0 before bit manipulation.✅ Add 'if n <= 0: return False' before bitwise check.

Wrong: true for negative numbers like -16 or -1Not excluding negative inputs before bitwise operations.✅ Add 'if n <= 0: return False' to exclude negatives.

Wrong: true for numbers with multiple bits set like 3 or 2147483647Incorrect bitwise condition; not using n & (n-1) == 0.✅ Use 'return n > 0 and (n & (n-1)) == 0' to check power of two.

Wrong: false for 1 or 2Off-by-one error or incorrect base case handling.✅ Ensure 1 and 2 return true by applying correct bitwise condition.

Wrong: TLE on large inputsUsing loop or recursion instead of O(1) bit manipulation.✅ Replace loop with 'return n > 0 and (n & (n-1)) == 0' for constant time.

✓

Test Cases

Focus on handling zero and negative inputs explicitly before bit checks.

Test inputs with multiple bits set to catch greedy or off-by-one mistakes.

Optimize your solution to O(1) time using bitwise operations.

t1_01basic

Input1

Expectedtrue

⏱ Performance - must finish in 2000ms

1 is 2^0, so it is a power of two.

💡 Recall that powers of two have exactly one bit set in binary.

💡 Check if n > 0 and n & (n-1) == 0 to confirm power of two.

💡 Return true if n > 0 and (n & (n-1)) == 0, else false.

Why it failed: Failed on canonical input 1: likely missed that 1 is a power of two. Fix by ensuring n=1 returns true and using n > 0 condition.

✓ Correctly identifies 1 as a power of two.

t1_02basic

Input16

Expectedtrue

⏱ Performance - must finish in 2000ms

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

💡 Try representing 16 in binary and count set bits.

💡 Use the n & (n-1) trick to check if only one bit is set.

💡 Return true if n > 0 and (n & (n-1)) == 0, else false.

Why it failed: Failed on input 16: likely incorrect bit manipulation or missing n > 0 check. Fix by applying n > 0 and n & (n-1) == 0 condition.

✓ Correctly identifies 16 as a power of two.

t2_01edge

Input0

Expectedfalse

⏱ Performance - must finish in 2000ms

0 is not a power of two by definition.

💡 Remember zero has no bits set and is not a power of two.

💡 Check that n must be strictly greater than zero.

💡 Return false if n <= 0 before applying bit tricks.

Why it failed: Returned true for 0: missing n > 0 guard. Fix by adding 'if n <= 0: return false' before bit check.

✓ Correctly returns false for 0.

t2_02edge

Input-16

Expectedfalse

⏱ Performance - must finish in 2000ms

Negative numbers are not powers of two.

💡 Negative numbers have sign bit set; powers of two are positive.

💡 Check that n must be positive before bit manipulation.

💡 Return false if n <= 0 to exclude negatives.

Why it failed: Returned true for negative input: missing n > 0 check. Fix by returning false if n <= 0.

✓ Correctly returns false for negative numbers.

t2_03edge

Input2147483647

Expectedfalse

⏱ Performance - must finish in 2000ms

2147483647 (2^31 - 1) is not a power of two.

💡 Largest 32-bit signed int has all bits set except sign bit.

💡 Check that n & (n-1) == 0 only for powers of two.

💡 Return false if more than one bit is set.

Why it failed: Returned true for 2147483647: incorrect bit check. Fix by ensuring n & (n-1) == 0 condition is strictly applied.

✓ Correctly returns false for 2147483647.

t2_04edge

Input1

Expectedtrue

⏱ Performance - must finish in 2000ms

1 is the exact boundary case (2^0) and must return true.

💡 Check the base case where n equals 1.

💡 Ensure n > 0 and n & (n-1) == 0 returns true for n=1.

💡 Return true if n == 1 or passes bit manipulation check.

Why it failed: Returned false for 1: off-by-one or boundary check missing. Fix by handling n=1 correctly.

✓ Correctly returns true for the exact boundary case 1.

t3_01corner

Input3

Expectedfalse

⏱ Performance - must finish in 2000ms

3 (binary 11) has two bits set, so not a power of two.

💡 Check how many bits are set in n's binary representation.

💡 Use n & (n-1) to clear the lowest set bit and test if result is zero.

💡 Return false if n & (n-1) != 0.

Why it failed: Returned true for 3: failed to check multiple bits set. Fix by using 'return n > 0 and (n & (n-1)) == 0'. This is the greedy trap test.

✓ Correctly identifies 3 is not a power of two.

t3_02corner

Input-1

Expectedfalse

⏱ Performance - must finish in 2000ms

-1 in two's complement has all bits set, not a power of two.

💡 Negative numbers have sign bit set and are invalid.

💡 Check n > 0 before bit manipulation.

💡 Return false if n <= 0 to exclude negatives.

Why it failed: Returned true for -1: missing n > 0 check. This is the negative input test.

✓ Correctly returns false for -1.

t3_03corner

Input2

Expectedtrue

⏱ Performance - must finish in 2000ms

2 is 2^1, a power of two.

💡 2 in binary is 10, only one bit set.

💡 Check n & (n-1) == 0 for powers of two.

💡 Return true if n > 0 and n & (n-1) == 0.

Why it failed: Returned false for 2: off-by-one or incorrect bit check. Fix by applying correct bit manipulation condition.

✓ Correctly identifies 2 as a power of two.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(1) bit manipulation performance within 2 seconds.

💡 Bit manipulation runs in constant time regardless of input size.

💡 Avoid loops or recursion that scale with input magnitude.

💡 Use n > 0 and n & (n-1) == 0 for O(1) check.

Why it failed: TLE due to using O(log n) or worse approach. Fix by using O(1) bit manipulation method.

✓ Algorithm runs in O(1) time as expected.

Practice

1. Consider the following code that generates all permutations of 3 elements using bitmask DP with iterative tabulation. What is the content of dp[7] after the loops finish?

def generate_permutations_iterative(n):
    dp = [[] for _ in range(1 << n)]
    dp[0] = [[]]
    for mask in range(1 << n):
        for i in range(n):
            if not (mask & (1 << i)):
                for perm in dp[mask]:
                    dp[mask | (1 << i)].append(perm + [i])
    return dp[(1 << n) - 1]

perms = generate_permutations_iterative(3)
print(perms)

easy

A. [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]

B. [[0,1,2], [1,0,2], [2,0,1]]

C. [[0,1,2], [0,2,1], [1,0,2], [2,1,0]]

D. [[0,1,2], [1,2,0], [2,1,0], [2,0,1]]

Solution

1. Step 1: Trace dp[0] initialization

   dp[0] starts with [[]], representing empty permutation.

2. Step 2: Iteratively build dp for all masks

   For each mask, append unused elements to existing permutations, eventually filling dp[7] with all permutations of [0,1,2].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[7] contains all 3! = 6 permutations of [0,1,2] [OK]

Hint: dp[(1<

Common Mistakes:

• Confusing mask indexing leading to missing permutations
• Off-by-one errors in bitmask checks

2. What is the output of the following code when the input is 11?

def hammingWeight(n: int) -> int:
    return bin(n).count('1')

print(hammingWeight(11))

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Convert 11 to binary

   11 in binary is 1011.

2. Step 2: Count '1's in '1011'

   There are three '1's in the string.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   bin(11) = '0b1011', count('1') = 3 [OK]

Hint: Count '1's in binary string representation [OK]

Common Mistakes:

• Counting bits incorrectly
• Confusing decimal and binary digits

3. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

4. The following code attempts to find the missing number using XOR. Which line contains the subtle bug that causes incorrect results when the missing number is n?

medium

A. Line 3: initializing xor_all to 0

B. Line 7: returning xor_all without modification

C. Line 4: iterating only to n-1 instead of n

D. Line 6: XORing array elements

Solution

1. Step 1: Analyze the loop range for XORing indices

   The loop runs from 0 to n-1 (range(n)), missing the number n itself.

2. Step 2: Understand impact on missing number detection

   Since n is not XORed, if n is the missing number, it won't be accounted for, causing wrong output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing loop to range(n+1) fixes the bug [OK]

Hint: Loop must include n to XOR all indices correctly [OK]

Common Mistakes:

• Off-by-one in loop range
• Forgetting to XOR n
• Assuming initialization causes bug

5. 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