algoadvance

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Clarifying Questions

Before diving into coding, let’s clarify the problem with a few questions:

1. What is the range of values for left and right?
   • Usually, they are 0 <= left <= right <= 2^31 - 1.
2. Are left and right inclusive?
   • Yes, the range [left, right] is inclusive.

Strategy

The key observation for solving this problem is that as numbers increase in a range, their lower bits will eventually flip to 0 due to the power-of-2 nature of binary representation:

• To find the bitwise AND of all the numbers in the range, we need to find common bits of left and right until they diverge. Once they differ, the remaining lower bits in a range [left, right] will be mismatched and thus zero out in the AND result.

Steps

1. Keep shifting left and right to the right until they are equal.
2. Count the number of shifts.
3. Shift left (or right, since now they are equal) back to the left by the same number of times to derive the result.

This effectively identifies the common prefix bits in the numbers within the range.

Code

Here is how you can implement this in Python:

def rangeBitwiseAnd(left: int, right: int) -> int:
    shift = 0
    # Find the common prefix
    while left < right:
        left >>= 1
        right >>= 1
        shift += 1
    # Shift the common prefix back to its original position
    return left << shift

Time Complexity

• The while loop continues until left is equal to right.
• In the worst case, if both numbers are very large and close to the upper limit of integer range, the loop will run log2(max_val) times, where max_val is the maximum integer value.
• Therefore, the time complexity is O(log n), where n is the range size or the magnitude of right.

This algorithm ensures that we efficiently find the bitwise AND of a range of numbers by focusing on their bits directly and iterating only until necessary.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?