Power of Two

▶

Steps

setup

Initialize input number

The input number n=1 is stored and converted into its 32-bit binary representation for bitwise operations.

💡 Representing the number in binary is essential to inspect individual bits for the power of two check.

Line:

def isPowerOfTwo(n: int) -> bool:

💡 The binary form of the number is the foundation for all subsequent bitwise checks.

compare

Check if n is less than or equal to zero

The algorithm checks if the input number n=1 is less than or equal to zero to handle invalid cases.

💡 Numbers less than or equal to zero cannot be powers of two, so this check quickly excludes them.

Line:

if n <= 0:

💡 Since n=1 is positive, the algorithm proceeds to count set bits.

fill_cells

Start counting set bits

Begin counting the number of bits set to 1 in the binary representation of n=1.

💡 Counting set bits reveals how many bits are active; a power of two has exactly one set bit.

Line:

return bin(n).count('1') == 1

💡 The count of set bits will determine the final answer.

compare

Inspect bit 31 (LSB)

Check the least significant bit (bit 31) which is 1, so increment the count of set bits.

💡 Each set bit increments the count; here the LSB is set, so count becomes 1.

Line:

bin(n).count('1')

💡 The first set bit found confirms at least one bit is set.

compare

Inspect bit 30

Check bit 30 which is 0, so the count remains unchanged.

💡 Bits that are zero do not affect the count of set bits.

Line:

bin(n).count('1')

💡 Only set bits increment the count; zero bits are skipped.

compare

Inspect bit 29

Check bit 29 which is 0, count remains 1.

💡 The algorithm continues checking bits from MSB to LSB.

Line:

bin(n).count('1')

💡 No additional set bits found so far.

compare

Inspect bit 28

Check bit 28 which is 0, count remains 1.

💡 Continuing the bit inspection from MSB towards LSB.

Line:

bin(n).count('1')

💡 Bit 28 is zero, so count remains unchanged.

compare

Inspect remaining bits 0 to 27

All remaining bits from 0 to 27 are zero, so the count remains 1.

💡 The algorithm confirms no other bits are set beyond the LSB.

Line:

bin(n).count('1')

💡 Only one bit is set in the entire 32-bit number.

compare

Compare count of set bits to 1

Check if the count of set bits (1) equals exactly 1 to determine if n is a power of two.

💡 A power of two has exactly one bit set; this comparison confirms that.

Line:

return bin(n).count('1') == 1

💡 Since count is 1, n=1 is a power of two.

reconstruct

Return True as final answer

The function returns True because the input number has exactly one set bit, confirming it is a power of two.

💡 The final return value indicates the result of the power of two check.

Line:

return bin(n).count('1') == 1

💡 The algorithm successfully identifies 1 as a power of two.

def isPowerOfTwo(n: int) -> bool:
    # STEP 2: Check if n <= 0
    if n <= 0:
        return False
    # STEP 3-8: Count set bits and compare
    return bin(n).count('1') == 1

if __name__ == '__main__':
    test_cases = [1, 16, 218, 0, -4]
    for num in test_cases:
        print(f'isPowerOfTwo({num}) = {isPowerOfTwo(num)}')

📊

Power of Two - Watch the Algorithm Execute, Step by Step

Watching each bit operation and decision helps you understand how bit counting reveals if a number is a power of two without complex math.

Initialize input

A

0

1

=1

B

Check if n <= 0

A

0

1

=1

B

💡 The number is positive, so we continue.

Check bit for counting

A

0

1

=1

B

────────────────

=

0

0

0

0

0

0

0

0

💡 Inspecting LSB to see if it is set.

Count set bit

A

0

1

=1

B

────

=

0

1

=1

💡 Set bit found at LSB, count = 1.

Check bit 30

A

0

1

=1

B

────

=

0

1

=1

💡 Bit 30 is zero, count unchanged.

Check bit 29

A

0

1

=1

B

────

=

0

1

=1

💡 Bit 29 is zero, count unchanged.

Check bit 28

A

0

1

=1

B

────

=

0

1

=1

💡 Bit 28 is zero, count unchanged.

Count set bits

A

0

1

=1

B

────

=

0

1

=1

💡 Only one bit set in entire number.

Compare count to 1

A

0

1

=1

B

────

=

0

1

=1

💡 Count matches 1, confirming power of two.

Return True

A

0

1

=1

B

────

=

0

1

=1

💡 Final answer: True

Key Takeaways

✓ A number is a power of two if and only if it has exactly one bit set in its binary representation.

This insight is hard to see from code alone because it requires understanding binary bit patterns, which the visualization makes explicit.

✓ Checking if the number is positive first quickly excludes invalid inputs without unnecessary bit counting.

This early check is a simple but important optimization that prevents wasted computation.

✓ Counting set bits one by one shows how the algorithm inspects every bit, even if most are zero.

Seeing each bit checked visually clarifies the process behind the built-in count function.

Practice

1. Consider the following code to find the missing number in an array containing numbers from 0 to n with one missing. What is the value of xor_all just before the return statement when the input is [3, 0, 1]?

easy

A. 2

B. 3

C. 0

D. 1

Solution

1. Step 1: Trace xor_all after first loop (XOR 0 to 3)

   0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 2 = 3, 3 ^ 3 = 0

2. Step 2: XOR xor_all with each array element

   0 ^ 3 = 3, 3 ^ 0 = 3, 3 ^ 1 = 2

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final xor_all is 2, the missing number [OK]

Hint: XOR all indices and elements cancels pairs leaving missing number [OK]

Common Mistakes:

• Off-by-one in range causing wrong xor_all
• XORing only array or only indices
• Misreading xor_all updates

2. Given the following Python code, what is the output of isPowerOfFour(16)?

easy

A. True

B. False

C. Raises an error due to floating point precision

D. None

Solution

1. Step 1: Calculate log2(16)

   log2(16) = 4, dividing by 2 gives 2.0.

2. Step 2: Check if 2.0 equals int(2.0)

   2.0 == 2 is True, so the function returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   16 is 4^2, so output True is expected [OK]

Hint: log2(16)/2 = 2.0 equals int(2) -> True

Common Mistakes:

• Assuming floating point error causes failure
• Confusing power of two with power of four

3. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?

medium

A. Line 8: set_bit calculation

B. Line 6: xor calculation loop

C. Line 3: xor initialization

D. Line 12: partitioning condition

Solution

1. Step 1: Identify how set_bit is computed

   Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.

2. Step 2: Understand impact of bug

   Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug in set_bit calculation breaks partitioning [OK]

Hint: Isolate rightmost set bit with xor & (-xor) [OK]

Common Mistakes:

• Using xor directly as set_bit
• Breaking early before full XOR
• Misusing partition condition

4. If the input number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors

5. If the input array can contain negative numbers, which modification is necessary for the optimal XOR and partition approach to correctly find the two unique numbers?

hard

A. No modification needed; the current approach works for negative numbers as is.

B. Use absolute values of numbers for XOR and partitioning to avoid sign issues.

C. Sort the array first to handle negative numbers before applying XOR partitioning.

D. Use set_bit = xor & (-xor) carefully, ensuring two's complement representation is handled correctly.

Solution

1. Step 1: Understand bitwise operations with negative numbers

   Negative numbers use two's complement; -xor computes two's complement correctly, so set_bit = xor & (-xor) works if implemented carefully.

2. Step 2: Identify necessary care

   Ensure language and environment handle negative bitwise operations properly; no need to sort or use absolute values.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct handling of two's complement is key for negative numbers [OK]

Hint: Two's complement handles negative bits; no sorting needed [OK]

Common Mistakes:

• Assuming XOR fails on negatives
• Sorting wastes time
• Using absolute values breaks uniqueness