Bitwise AND of Numbers Range

MEDIUM

Description

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 <= 2³¹ - 1

Approaches

Checkout 3 different approaches to solve Bitwise AND of Numbers Range. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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

Algorithm

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

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 Analysis

Time Complexity: O(right - left) in the worst caseSpace Complexity: O(1)

Pros and Cons

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]

Code Solutions

Checking out 5 solutions in different languages for Bitwise AND of Numbers Range. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Bitwise AND of Numbers Range

Patterns:

Bit Manipulation

Companies:

Google |