grid47 Exploring patterns and algorithms
Oct 17, 2024
5 min read
Solution to LeetCode 201: Bitwise AND of Numbers Range Problem
Given two integers, left and right, representing a range [left, right], you need to calculate the bitwise AND of all numbers within that range, inclusive. The bitwise AND operation takes two numbers and returns a number where each bit is set to 1 if the corresponding bits of both numbers are also 1.
Problem
Approach
Steps
Complexity
Input: The input consists of two integers: left and right, representing the range [left, right].
Example: left = 10, right = 12
Constraints:
• 0 <= left <= right <= 231 - 1
Output: Return the result of the bitwise AND operation of all numbers between left and right, inclusive.
Example: Output: 8
Constraints:
• The output should be a single integer representing the result of the bitwise AND.
Goal: The goal is to efficiently calculate the bitwise AND of all numbers in the range [left, right].
Steps:
• Shift the left and right integers to the right until they become equal. Each time they are not equal, shift both numbers to the right by 1 bit.
• Count how many shifts were needed. The final result will be the right-shifted value of either left or right shifted back by the counted number of shifts.
Goal: The range of the integers is from 0 to 231 - 1, and the number of bits to consider is at most 32.
Steps:
• 0 <= left <= right <= 231 - 1
Assumptions:
• Both left and right are within the given constraints.
• Input: left = 10, right = 12
• Explanation: In this example, the numbers between 10 and 12 are 10, 11, and 12. The bitwise AND of these numbers is 8, because 10 (1010 in binary), 11 (1011 in binary), and 12 (1100 in binary) all share the prefix 1000.
• Input: left = 0, right = 0
• Explanation: If left and right are both 0, the bitwise AND of the range [0, 0] is 0.
• Input: left = 1, right = 2147483647
• Explanation: In this case, the bitwise AND of all numbers from 1 to 2147483647 will result in 0, because at least one bit in every position will be different across such a large range.
Approach: To solve the problem efficiently, we can use bitwise operations. The key observation is that as we move from left to right in the range, the bits of the numbers are guaranteed to become different at some point. The bitwise AND operation for such a range will result in a number that preserves only the common prefix of the numbers.
Observations:
• The range can be large, so a brute force approach of calculating the AND for every number is inefficient.
• Shifting the numbers to the right and comparing them allows us to determine the common prefix.
• By shifting the numbers to the right, we ensure that we are comparing the most significant bits, where the AND result will change the least. Once the numbers are equal, we can shift them back and return the result.
Steps:
• Initialize a variable shift to track the number of right shifts needed.
• While left is not equal to right, shift both left and right to the right by 1 bit, and increment the shift count.
• Once the numbers are equal, shift right back by the number of shifts and return the result.
Empty Inputs:
• The range [0, 0] should return 0.
Large Inputs:
• For very large ranges, the solution should be efficient enough to handle up to 231 - 1.
Special Values:
• If left equals right, the result is simply left (or right), since the AND of a single number is the number itself.
Constraints:
• Ensure the solution handles large inputs efficiently within the constraints.
intrangeBitwiseAnd(int left, int right) {
int shift =0;
while(right != left)
{
right >>=1 ;
left >>=1;
shift++;
}
return right << shift;
}
1 : Function Definition
intrangeBitwiseAnd(int left, int right) {
Define the function 'rangeBitwiseAnd' which takes two integers, 'left' and 'right', and returns the result of the bitwise AND operation for all integers in the range [left, right].
2 : Variable Initialization
int shift =0;
Initialize a variable 'shift' to track the number of right shifts performed to align 'left' and 'right'.
3 : Loop Condition
while(right != left)
Check if 'right' and 'left' are not equal. If they are different, continue shifting them to the right until they become the same.
4 : Right Shift
right >>=1 ;
Perform a right shift on 'right' by 1 bit, effectively halving the value and moving the binary representation to the right.
5 : Left Shift
left >>=1;
Perform a right shift on 'left' by 1 bit, similar to the operation on 'right'. This ensures both numbers are compared at the same binary position.
6 : Shift Counter Increment
shift++;
Increment the shift counter to keep track of the number of right shifts performed.
7 : Return Shifted Result
return right << shift;
Once 'left' and 'right' are equal, shift the 'right' value back to the left by the number of times we shifted in the loop, effectively returning the bitwise AND result for the entire range.
Best Case: O(1)
Average Case: O(log(max(left, right)))
Worst Case: O(log(max(left, right)))
Description: In the worst case, the algorithm performs a logarithmic number of shifts, which corresponds to the number of bits in the largest number.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant because only a few integer variables are used, regardless of the size of the input.
