Bit Manipulation - Gray Code
What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula
[i ^ (i >> 1) for i in range(1 << n)]?What is the time complexity of generating an n-bit Gray code sequence using the optimal bitwise formula [i ^ (i >> 1) for i in range(1 ?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze the loop iteration count
The list comprehension iterates over all integers from 0 to 2^n - 1, so 2^n iterations.Step 2: Analyze work per iteration
Each iteration performs constant time bitwise operations (XOR and right shift), so O(1) per iteration.Final Answer:
Option D -> Option DQuick Check:
Total time is proportional to 2^n, not multiplied by n or factorial [OK]
Quick Trick: Loop runs 2^n times with O(1) work each [OK]
Common Mistakes:
MISTAKES- Confusing n with 2^n and claiming O(n)
- Assuming bitwise operations cost O(n)
- Mistaking factorial complexity from brute force backtracking
Trap Explanation:
PITFALL- Option C looks plausible if candidate thinks bitwise ops cost O(n), and factorial complexity is a common confusion from brute force.
Interviewer Note:
CONTEXT- Tests if candidate understands exponential growth and constant-time bitwise operations.
Master "Gray Code" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes