Bit Manipulation - Power of Two
What is the space complexity of the recursive brute force approach that divides n by 2 repeatedly to check if it is a power of two?
What is the space complexity of the recursive brute force approach that divides n by 2 repeatedly to check if it is a power of two?
medium🪤 Complexity Trap Q6 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand recursion depth
Each recursive call divides n by 2, so recursion depth is O(log n).Step 2: Consider call stack space
Each call uses stack space, so total auxiliary space is O(log n).Step 3: Trap explanation
However, if the implementation uses extra space per call (e.g., copying data), space can be higher, but standard recursion stack is O(log n).Final Answer:
Option A -> Option AQuick Check:
Recursive call stack grows with log n depth [OK]
Quick Trick: Recursive stack depth is O(log n) [OK]
Common Mistakes:
MISTAKES- Forgetting recursion stack space
- Assuming constant space for recursion
Trap Explanation:
PITFALL- Candidates often forget recursion stack space, assuming O(1) space.
Interviewer Note:
CONTEXT- Tests understanding of recursion space complexity.
Master "Power of Two" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes