Check if Number is Power of Two in DSA Python - Time & Space Complexity

Time Complexity: Check if Number is Power of Two

O(1)

Understanding Time Complexity

We want to know how fast we can check if a number is a power of two.

How does the time to check grow as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def is_power_of_two(n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

This code checks if a number is a power of two using a bitwise trick.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single bitwise AND operation and subtraction.
• How many times: Exactly once, no loops or recursion.

How Execution Grows With Input

The number of steps stays the same no matter how big the number is.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The work does not increase as the number grows.

Final Time Complexity

Time Complexity: O(1)

This means the check takes the same amount of time no matter how large the number is.

Common Mistake

[X] Wrong: "Checking if a number is a power of two requires looping through all smaller numbers."

[OK] Correct: This bitwise method does the check instantly without loops, so it is much faster.

Interview Connect

Knowing this quick check shows you understand efficient bitwise operations, a useful skill in many coding problems.

Self-Check

"What if we changed the input to allow zero and negative numbers? How would the time complexity change?"

Practice

1. Which of the following numbers is a power of two?

easy

A. 16

B. 18

C. 20

D. 22

Solution

1. Step 1: Understand powers of two

   Powers of two are numbers like 1, 2, 4, 8, 16, 32, etc., where each is 2 raised to an integer.

2. Step 2: Check each option

   16 = 2^4, so it is a power of two. Others like 18, 20, 22 are not powers of two.

3. Final Answer:

   16 -> Option A

4. Quick Check:

   16 = 2^4 [OK]

Hint: Only numbers with one '1' bit in binary are powers of two [OK]

Common Mistakes:

• Confusing even numbers with powers of two
• Thinking any multiple of 2 is a power of two

2. Which of the following Python expressions correctly checks if n is a power of two?

easy

A. n | (n - 1) == 0

B. n & (n - 1) == 0

C. n ^ (n - 1) == 0

D. n + (n - 1) == 0

Solution

1. Step 1: Understand bitwise AND check

   For powers of two, binary form has only one '1'. n & (n-1) clears the lowest set bit. If result is 0, n is power of two.

2. Step 2: Analyze options

   n & (n - 1) == 0 uses correct bitwise AND check. Others use OR, XOR, or addition which do not correctly check power of two.

3. Final Answer:

   n & (n - 1) == 0 -> Option B

4. Quick Check:

   Bitwise AND check is standard for power of two [OK]

Hint: Use n & (n-1) == 0 to check power of two [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Forgetting to check n > 0 before this test

3. What is the output of the following code?

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(32))
print(is_power_of_two(45))

medium

A. False\nFalse

B. False\nTrue

C. True\nFalse

D. True\nTrue

Solution

1. Step 1: Check 32

   32 is 2^5, so n > 0 and n & (n-1) == 0 is True.

2. Step 2: Check 45

   45 is not a power of two, so n & (n-1) != 0, returns False.

3. Final Answer:

   True\nFalse -> Option C

4. Quick Check:

   32 power of two = True, 45 not = False [OK]

Hint: Check output for known powers of two and non-powers [OK]

Common Mistakes:

• Ignoring n > 0 condition
• Assuming all even numbers are powers of two

4. Find the error in this code snippet that checks if a number is a power of two:

def check_power(n):
    if n & (n - 1) == 0:
        return True
    else:
        return False

print(check_power(0))

medium

A. Missing check for n > 0 before bitwise operation

B. No error, code works fine

C. Should use OR instead of AND

D. Return values should be strings 'True' or 'False'

Solution

1. Step 1: Analyze bitwise check

   n & (n-1) == 0 works only if n > 0. For n=0, it returns True incorrectly.

2. Step 2: Identify missing condition

   Code lacks n > 0 check, so 0 incorrectly returns True.

3. Final Answer:

   Missing check for n > 0 before bitwise operation -> Option A

4. Quick Check:

   Always check n > 0 before bitwise test [OK]

Hint: Always check n > 0 before bitwise power of two test [OK]

Common Mistakes:

• Not handling zero or negative inputs
• Using wrong bitwise operators

5. You want to filter a list to keep only numbers that are powers of two. Which code snippet correctly does this?

nums = [0, 1, 2, 3, 4, 5, 8, 16, 18]

A) result = [x for x in nums if x & (x - 1) == 0]
B) result = [x for x in nums if x > 0 and x & (x - 1) == 0]
C) result = [x for x in nums if x | (x - 1) == 0]
D) result = [x for x in nums if x > 0 or x & (x - 1) == 0]

hard

A. result = [x for x in nums if x & (x - 1) == 0]

B. result = [x for x in nums if x > 0 or x & (x - 1) == 0]

C. result = [x for x in nums if x | (x - 1) == 0]

D. result = [x for x in nums if x > 0 and x & (x - 1) == 0]

Solution

1. Step 1: Understand filtering condition

   We must check x > 0 to avoid zero or negative numbers passing the test.

2. Step 2: Analyze each option

   result = [x for x in nums if x > 0 and x & (x - 1) == 0] correctly uses x > 0 and bitwise check. result = [x for x in nums if x & (x - 1) == 0] misses x > 0, so 0 passes incorrectly. Options C and D use wrong operators or logic.

3. Final Answer:

   result = [x for x in nums if x > 0 and x & (x - 1) == 0] -> Option D

4. Quick Check:

   Filter with x > 0 and bitwise AND check [OK]

Hint: Filter with x > 0 and x & (x-1) == 0 for powers of two [OK]

Common Mistakes:

• Not filtering out zero
• Using OR instead of AND in condition
• Using bitwise OR instead of AND