Scale Engineer

Bitwise AND of Numbers Range

Med
#0189Time: O(right - left) in the worst caseSpace: O(1)1 company
Patterns
Bit Manipulation
Companies
Google

Prompt

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

 

Constraints:

  • 0 <= left <= right <= 231 - 1

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to perform a bitwise AND operation on all numbers in the range [left, right] one by one.

Algorithm

  1. Initialize result with the value of left
  2. Iterate from left + 1 to right:
    • Update result = result & current_number
    • If result becomes 0, break the loop (optimization)
  3. Return result

Walkthrough

In this approach, we iterate through all numbers from left to right and perform a bitwise AND operation on each number with the result of previous operations.

public int rangeBitwiseAnd(int left, int right) {    int result = left;    for (int i = left + 1; i <= right; i++) {        result &= i;        // If result becomes 0, any further AND operations will remain 0        if (result == 0) {            break;        }    }    return result;}

This approach works correctly for small ranges, but it will time out for large ranges like [1, 2147483647] because we would need to perform billions of operations.

Complexity

Time

O(right - left) in the worst case

Space

O(1)

Trade-offs

Pros

  • Simple and easy to understand

  • Works well for small ranges

Cons

  • Very inefficient for large ranges

  • Will time out for inputs like [1, 2147483647]

Solutions

public class Solution {    public int RangeBitwiseAnd(int left, int right) {        while (left < right) {            right &= (right - 1);        }        return right;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem