Bitwise AND of Numbers Range
Medium · Bit Manipulation · Bit Manipulation
Problem
You are given two integers left and right with left <= right. Return the bitwise AND of every integer from left to right, inclusive.
The range can hold about two billion numbers, so walking through all of them is too slow. Look for what the numbers in the range must have in common.
Examples
Input: left = 12, right = 15 Output: 12
12 to 15 are 1100, 1101, 1110 and 1111. They all start with 11, and each of the two low bits is 0 somewhere, so 1100 = 12 is left.
Input: left = 5, right = 8 Output: 0
7 is 0111 and 8 is 1000: they share no bit, so the AND is 0.
Input: left = 9, right = 9 Output: 9
A single number ANDed with itself is unchanged.
Constraints
- 0 <= left <= right <= 2^31 - 1
Approaches
- AND every number, stop at zero — time O(right - left) in the worst case, space O(1)
Follow-up
What about the bitwise OR of the range? It is the same common prefix, now followed by ones instead of zeros, because every lower bit is 1 in some number of the range.
Related problems
Start free on Cariara · Coding problems · System design studio
