Jobs

Interviews

Discussions

Bitwise AND of Numbers Range

Medium

Asked by:

More companies

47 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Bitwise AND of Numbers Range

Medium

Asked by:

47 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of 'left' and 'right'? (e.g., maximum and minimum values, and the data type used to represent them)?
Can 'left' be greater than 'right'? If so, what should I return?
If 'left' and 'right' are equal, should I just return that value?
Are 'left' and 'right' non-negative?
Are there any specific memory constraints I should be aware of, given the potential range of 'left' and 'right'?

Brute Force Solution

Approach

The brute force approach to finding the bitwise AND of a range of numbers involves directly calculating the bitwise AND. We'll do this by looking at each number in the range one at a time and updating our running bitwise AND value.

Here's how the algorithm would work step-by-step:

Start with the first number in the range as our initial result.
Go through each of the remaining numbers in the range, one by one.
For each number, perform a bitwise AND operation between our current result and the number.
Update our result with the value obtained from that bitwise AND operation.
After going through all the numbers in the range, the final result will be the answer we are looking for.

Code Implementation

def range_bitwise_and_brute_force(range_start, range_end):
    # Initialize the result with the starting number in the range
    bitwise_and_result = range_start

    # Iterate through the numbers in the range (excluding the start)
    for current_number in range(range_start + 1, range_end + 1):
        # Update the result by bitwise ANDing with the current number
        bitwise_and_result = bitwise_and_result & current_number

    return bitwise_and_result

Big(O) Analysis

Time Complexity

O(m) – The described algorithm iterates through a range of numbers, where 'm' represents the size of the range (i.e., `right - left + 1`). In each iteration, a bitwise AND operation is performed. Therefore, the time complexity is directly proportional to the number of elements in the range. Thus, the algorithm performs approximately 'm' operations, resulting in a time complexity of O(m).

Space Complexity

O(1) – The provided algorithm initializes a single variable to store the running bitwise AND result. The algorithm iterates through the numbers in the range, updating this variable in place. No additional data structures that scale with the size of the input range (N = right - left + 1) are created or used. Therefore, the auxiliary space required remains constant regardless of the input size.

Optimal Solution

Approach

The goal is to find the common bits that are set across all numbers in the given range. The efficient way to do this involves identifying and eliminating the differing bits from the right until we reach a common prefix.

Here's how the algorithm would work step-by-step:

Keep shifting both numbers to the right until they become equal.
Count how many shifts you performed.
Shift the equal number back to the left by the number of shifts you counted.
The resulting number is the bitwise AND of the range.

Code Implementation

def range_bitwise_and(left_number, right_number):
    shift_count = 0

    # Keep shifting until the numbers are equal.
    while left_number != right_number:
        left_number >>= 1
        right_number >>= 1
        shift_count += 1

    # Common bits found, shift back to original position.
    return left_number << shift_count

Big(O) Analysis

Time Complexity

O(log n) – The while loop iterates until 'left' and 'right' become equal by right shifting both numbers. The number of shifts is determined by how many bits differ between 'left' and 'right'. The maximum number of differing bits is related to the number of bits needed to represent the input number 'n', which is log base 2 of n (written as log n). The bitwise shift operation inside the loop takes constant time. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm uses only a constant amount of extra memory. Specifically, it uses an integer to count the number of shifts performed and potentially a variable to store the shifted value. These variables occupy a fixed amount of space regardless of the input range (the values of the start and end numbers), and thus the auxiliary space is constant. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
left > right	If left > right, the range is invalid, and the bitwise AND is effectively 0, so return 0.
left == right	If left equals right, the range consists of a single number; return that number (left).
left and right are both 0	If both are 0, then result is 0.
left is 0, right is a large number	This requires bitwise ANDing 0 with every number up to right, resulting in 0; algorithm needs to handle large ranges efficiently.
left and right are consecutive powers of 2	Bitwise AND of two consecutive powers of 2 will be 0.
left and right are very large numbers close to the maximum integer value	The bitwise AND operation must be performed accurately without integer overflow or unexpected behavior when working with large values.
left and right differ by only one	Handles this normally, doing the bitwise AND of only those two numbers.
Large difference between left and right (e.g., left = 1, right = 2^31 - 1)	Algorithm's time complexity should be logarithmic to avoid timeout issues related to large differences.

left > right

How to Handle:

If left > right, the range is invalid, and the bitwise AND is effectively 0, so return 0.

left == right

How to Handle:

If left equals right, the range consists of a single number; return that number (left).

left and right are both 0

How to Handle:

If both are 0, then result is 0.

left is 0, right is a large number

How to Handle:

This requires bitwise ANDing 0 with every number up to right, resulting in 0; algorithm needs to handle large ranges efficiently.

left and right are consecutive powers of 2

How to Handle:

Bitwise AND of two consecutive powers of 2 will be 0.

left and right are very large numbers close to the maximum integer value

How to Handle:

The bitwise AND operation must be performed accurately without integer overflow or unexpected behavior when working with large values.

left and right differ by only one

How to Handle:

Handles this normally, doing the bitwise AND of only those two numbers.

Large difference between left and right (e.g., left = 1, right = 2^31 - 1)

How to Handle:

Algorithm's time complexity should be logarithmic to avoid timeout issues related to large differences.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of 'left' and 'right'? (e.g., maximum and minimum values, and the data type used to represent them)?
Can 'left' be greater than 'right'? If so, what should I return?
If 'left' and 'right' are equal, should I just return that value?
Are 'left' and 'right' non-negative?
Are there any specific memory constraints I should be aware of, given the potential range of 'left' and 'right'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the range as our initial result.
Go through each of the remaining numbers in the range, one by one.
For each number, perform a bitwise AND operation between our current result and the number.
Update our result with the value obtained from that bitwise AND operation.
After going through all the numbers in the range, the final result will be the answer we are looking for.

Code Implementation

def range_bitwise_and_brute_force(range_start, range_end):
    # Initialize the result with the starting number in the range
    bitwise_and_result = range_start

    # Iterate through the numbers in the range (excluding the start)
    for current_number in range(range_start + 1, range_end + 1):
        # Update the result by bitwise ANDing with the current number
        bitwise_and_result = bitwise_and_result & current_number

    return bitwise_and_result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Keep shifting both numbers to the right until they become equal.
Count how many shifts you performed.
Shift the equal number back to the left by the number of shifts you counted.
The resulting number is the bitwise AND of the range.

Code Implementation

def range_bitwise_and(left_number, right_number):
    shift_count = 0

    # Keep shifting until the numbers are equal.
    while left_number != right_number:
        left_number >>= 1
        right_number >>= 1
        shift_count += 1

    # Common bits found, shift back to original position.
    return left_number << shift_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
left > right	If left > right, the range is invalid, and the bitwise AND is effectively 0, so return 0.
left == right	If left equals right, the range consists of a single number; return that number (left).
left and right are both 0	If both are 0, then result is 0.
left is 0, right is a large number	This requires bitwise ANDing 0 with every number up to right, resulting in 0; algorithm needs to handle large ranges efficiently.
left and right are consecutive powers of 2	Bitwise AND of two consecutive powers of 2 will be 0.
left and right are very large numbers close to the maximum integer value	The bitwise AND operation must be performed accurately without integer overflow or unexpected behavior when working with large values.
left and right differ by only one	Handles this normally, doing the bitwise AND of only those two numbers.
Large difference between left and right (e.g., left = 1, right = 2^31 - 1)	Algorithm's time complexity should be logarithmic to avoid timeout issues related to large differences.

left > right

How to Handle:

If left > right, the range is invalid, and the bitwise AND is effectively 0, so return 0.

left == right

How to Handle:

If left equals right, the range consists of a single number; return that number (left).

left and right are both 0

How to Handle:

If both are 0, then result is 0.

left is 0, right is a large number

How to Handle:

This requires bitwise ANDing 0 with every number up to right, resulting in 0; algorithm needs to handle large ranges efficiently.

left and right are consecutive powers of 2

How to Handle:

Bitwise AND of two consecutive powers of 2 will be 0.

left and right are very large numbers close to the maximum integer value

How to Handle:

The bitwise AND operation must be performed accurately without integer overflow or unexpected behavior when working with large values.

left and right differ by only one

How to Handle:

Handles this normally, doing the bitwise AND of only those two numbers.

Large difference between left and right (e.g., left = 1, right = 2^31 - 1)

How to Handle:

Algorithm's time complexity should be logarithmic to avoid timeout issues related to large differences.