Bit Manipulation - Bitwise AND of Numbers Range
What is the worst-case time complexity of the optimal algorithm that computes bitwise AND of numbers in range [left, right] by repeatedly right-shifting both until they are equal?
What is the worst-case time complexity of the optimal algorithm that computes bitwise AND of numbers in range [left, right] by repeatedly right-shifting both until they are equal?
medium📊 Complexity Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand the algorithm
The algorithm right shifts both numbers until they become equal, counting the shifts.Step 2: Analyze shifts
Each shift removes the least significant bit, so the number of shifts is at most the number of bits in the numbers.Step 3: Time complexity
Since integers have at mostlog2(right)bits, the time complexity is O(log(right)).Final Answer:
Option B -> Option BQuick Check:
Shifts bounded by bit length [OK]
Quick Trick: Number of shifts ≤ bit length of right [OK]
Common Mistakes:
MISTAKES- Assuming linear time over range size
- Confusing with brute force iteration
- Ignoring bit length limits
Trap Explanation:
PITFALL- Mistaking range size for complexity instead of bit length.
Interviewer Note:
CONTEXT- Tests understanding of time complexity of bitwise AND range algorithm.
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