Bit Manipulation - Bitwise AND of Numbers Range
What is the time complexity of the optimal bitwise AND range algorithm that repeatedly clears the rightmost set bit of the upper bound until it is less than or equal to the lower bound?
What is the time complexity of the optimal bitwise AND range algorithm that repeatedly clears the rightmost set bit of the upper bound until it is less than or equal to the lower bound?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand the loop behavior
Each iteration clears the rightmost set bit of right, reducing the number of set bits.Step 2: Count iterations
The loop runs at most as many times as there are set bits in the difference between right and left, i.e., the differing bits.Final Answer:
Option C -> Option CQuick Check:
Time depends on differing bits, not full range size [OK]
Quick Trick: Loop runs per differing set bit, not per number in range [OK]
Common Mistakes:
MISTAKES- Assuming linear in range size
- Confusing log n with bit count
- Ignoring bit-clearing effect
Trap Explanation:
PITFALL- O(n) looks plausible since range size matters, but bit-clearing reduces iterations drastically.
Interviewer Note:
CONTEXT- Checks if candidate understands bit-level iteration cost, not naive range iteration.
Master "Bitwise AND of Numbers Range" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes