Check if Number is Power of Two in DSA C - 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.

The question is: how does the time needed change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdbool.h>

bool isPowerOfTwo(unsigned int n) {
    return (n & (n - 1)) == 0 && n != 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 a subtraction.
• How many times: Exactly once, no loops or recursion.

How Execution Grows With Input

Since the code does only one check regardless of input size, the time stays the same.

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

Pattern observation: The number of operations does not grow with input size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

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

Common Mistake

[X] Wrong: "We need to divide or loop through the number to check if it is a power of two."

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

Interview Connect

Knowing this quick check shows you understand bitwise operations and efficiency, a skill valued in many coding challenges.

Self-Check

"What if we changed the input type to a signed integer? How would the time complexity change?"

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It has exactly one bit set to 1 in its binary form.

B. It is always an odd number.

C. It is divisible by 3.

D. It has all bits set to 1 in its binary form.

Solution

1. Step 1: Understand binary representation of powers of two

   A power of two in binary has exactly one '1' bit and the rest are '0's. For example, 4 is 100 in binary.

2. Step 2: Analyze the options

   It has exactly one bit set to 1 in its binary form. matches the binary property of powers of two. Options B, C, and D do not describe powers of two correctly.

3. Final Answer:

   It has exactly one bit set to 1 in its binary form. -> Option A

4. Quick Check:

   Power of two = one '1' bit [OK]

Hint: Power of two has only one '1' bit in binary [OK]

Common Mistakes:

• Thinking powers of two are always odd
• Assuming powers of two have multiple '1' bits
• Confusing divisibility rules

2. Which of the following C code snippets correctly checks if an integer n is a power of two?

easy

A. if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ }

B. if (n | (n - 1)) { /* power of two */ } else { /* not power of two */ }

C. if (n & (n + 1)) { /* power of two */ } else { /* not power of two */ }

D. if (n ^ (n - 1)) { /* power of two */ } else { /* not power of two */ }

Solution

1. Step 1: Understand bitwise check for power of two

   The expression n & (n - 1) is zero only if n is a power of two.

2. Step 2: Analyze each option

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } uses the correct expression. Options A, C, and D use incorrect bitwise operations that do not correctly check for power of two.

3. Final Answer:

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } -> Option A

4. Quick Check:

   n & (n-1) == 0 means power of two [OK]

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

Common Mistakes:

• Using OR instead of AND in bitwise check
• Using n + 1 instead of n - 1
• Confusing XOR with AND

3. What is the output of the following C code snippet?

int n = 16;
if (n & (n - 1))
    printf("No\n");
else
    printf("Yes\n");

medium

A. Runtime error

B. No

C. Compilation error

D. Yes

Solution

1. Step 1: Calculate n & (n - 1) for n = 16

   16 in binary is 10000. 15 is 01111. Bitwise AND: 10000 & 01111 = 00000 (0).

2. Step 2: Check condition and output

   Since the result is 0, the else block executes, printing "Yes".

3. Final Answer:

   Yes -> Option D

4. Quick Check:

   16 & 15 = 0 means power of two [OK]

Hint: If n & (n-1) is zero, print Yes [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Confusing output branches
• Assuming non-zero means power of two

4. Identify the error in the following C code that checks if n is a power of two:

int n = 10;
if (n & n - 1 == 0)
    printf("Power of two\n");
else
    printf("Not power of two\n");

medium

A. No error, code is correct

B. Missing parentheses around (n - 1) in bitwise operation

C. Incorrect variable initialization

D. Using bitwise OR instead of AND

Solution

1. Step 1: Analyze operator precedence in condition

   In C, == has higher precedence than &, so expression is evaluated as n & ((n - 1) == 0) which is incorrect.

2. Step 2: Correct the expression with parentheses

   Use (n & (n - 1)) == 0 to ensure correct evaluation.

3. Final Answer:

   Missing parentheses around (n - 1) in bitwise operation -> Option B

4. Quick Check:

   Use parentheses to fix precedence [OK]

Hint: Add parentheses: (n & (n - 1)) == 0 [OK]

Common Mistakes:

• Ignoring operator precedence
• Not using parentheses in bitwise expressions
• Assuming code compiles correctly without fix

5. You want to write a function in C that returns 1 if a number n is a power of two and 0 otherwise. Which of the following implementations correctly handles the case when n is zero or negative?

hard

A. int isPowerOfTwo(int n) { return n >= 0 && (n & (n + 1)) == 0; }

B. int isPowerOfTwo(int n) { return (n & (n - 1)) == 0; }

C. int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

D. int isPowerOfTwo(int n) { return n != 0 || (n & (n - 1)) == 0; }

Solution

1. Step 1: Consider zero and negative inputs

   Zero and negative numbers are not powers of two, so the function must exclude them.

2. Step 2: Analyze each function

   int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } checks if n > 0 and then applies the bitwise check correctly. int isPowerOfTwo(int n) { return (n & (n - 1)) == 0; } misses the positive check. Options A, B, and D use incorrect logic or operators.

3. Final Answer:

   int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } -> Option C

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Check n > 0 before bitwise test to avoid errors [OK]

Common Mistakes:

• Not handling zero or negative inputs
• Using wrong bitwise operators
• Using OR instead of AND in conditions