0

You need to determine if a given positive integer is a power of two. Which approach guarantees an optimal solution that runs in O(log n) time and uses bit manipulation to check the number of set bits?

easy🔍 Pattern Recognition Q11 of Q15

Bit Manipulation - Power of Two

You need to determine if a given positive integer is a power of two. Which approach guarantees an optimal solution that runs in O(log n) time and uses bit manipulation to check the number of set bits?

ARepeatedly divide the number by 2 and check if the remainder is ever non-zero.

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

CUse a greedy approach to subtract powers of two until the number reaches zero.

DUse dynamic programming to store results for smaller numbers and build up.

Step-by-Step Solution

Solution:

Step 1: Understand the problem requirement
The problem is to check if a number has exactly one set bit in its binary representation, which is true only for powers of two.
Step 2: Identify the optimal bit manipulation approach
The trick n & (n - 1) clears the lowest set bit. If the result is zero, it means there was only one set bit. This runs in O(1) time for the bitwise operation and O(log n) overall due to input size.
Final Answer:
Option B -> Option B
Quick Check:
n & (n - 1) == 0 only for powers of two [OK]

Quick Trick: n & (n-1) clears one set bit [OK]

Common Mistakes:

MISTAKES

Confusing greedy subtraction with bit checks
Using DP unnecessarily
Assuming division is faster than bit ops

Trap Explanation:

PITFALL

Repeated division looks intuitive but is slower and less elegant than bit manipulation.

Interviewer Note:

CONTEXT

Tests if candidate recognizes the classic bit manipulation pattern for power of two.

Master "Power of Two" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Bit Manipulation Quizzes