Bitwise AND of Numbers Range
mediumTime: O(log n)Space: O(1)
Recognize the pattern
AND of all numbers in rangecommon binary prefixdiffering bits become 0
Brute force idea
AND all numbers — O(range). Very slow for large ranges.
Better approach
Shift both left and right until equal. That's the common prefix. Shift back. O(32) = O(1).
Key invariant
Any bit where left and right differ = 0 in result. Common prefix = the AND result.
Watch out for
Trying to AND all numbers — the bit-prefix approach is O(1).