259. Range AND
A firewall rule combines a whole block of consecutive addresses at once: given two bounds, it takes every integer from left to right inclusive and merges them with a bitwise AND, producing a mask that keeps only the bits set in every address of the block.
Given left and right, return the bitwise AND of all integers n with left <= n <= right. The range can contain over two billion numbers, so looping through it is not an option; your solution must run in O(log(right)) time using O(1) space.
For example, the AND of every integer from 12 to 15 is 12, while the AND of 7 to 8 is 0.
Example 1
- Input:
- left = 20, right = 23
- Output:
- 20
- Explanation:
The numbers from 20 to 23 share only the binary prefix 101, so the AND is 20.
Example 2
- Input:
- left = 26, right = 33
- Output:
- 0
- Explanation:
The numbers from 26 to 33 share only the binary prefix nothing (0), so the AND is 0.
Example 3
- Input:
- left = 77, right = 77
- Output:
- 77
- Explanation:
The numbers from 77 to 77 share only the binary prefix 1001101, so the AND is 77.
Constraints
0 ≤ left ≤ right ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log right)
- Space
- O(1)