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 - 1The key idea in #201 Bitwise AND of Numbers Range is understanding how the bitwise AND operation behaves across a continuous range of numbers. As numbers increase within a range, the least significant bits tend to flip frequently, causing them to become 0 in the final AND result. The only bits that remain set are the common leftmost prefix bits shared by both boundaries of the range.
A common approach is to repeatedly shift both left and right to the right until they become equal. This effectively removes the differing lower bits. Once the numbers match, shifting the result back to its original position reconstructs the shared prefix, which is the final answer.
This method is efficient because it focuses only on the differing bits instead of iterating through every number in the range. The time complexity depends on the number of bits in the integers, making it very fast for typical 32-bit values while using constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Common Prefix via Bit Shifting | O(log n) | O(1) |
| Brute Force AND Across Range | O(n) | O(1) |
Techdose
This approach involves reducing the problem to finding a common ancestor in the binary tree representation of the numbers. When calculating the bitwise AND for numbers between left and right, we repeatedly right shift both numbers until they become equal, which means they share the same common prefix. The result will be left << the number of shifts.
Time Complexity: O(log N), where N is the range defined by right - left.
Space Complexity: O(1), no additional space required.
1function rangeBitwiseAnd(left, right) {
2 let shift = 0;
3 while (left < right) {
4 left >>= 1;
JavaScript Explanation:In JavaScript, this function performs bitwise operations similarly to other languages and logs the result using console.
In this approach, we find the common prefix of the binary representations of the numbers in the range. This is achieved by continually shifting the left and right numbers until they become equal. The remaining value after shifting is the common prefix, which gives the result after reversing the shifts.
Time Complexity: O(log N), where N is the range between left and right, depending on how many bits need to be cleared.
Space Complexity: O(1).
using namespace std;
int rangeBitwiseAnd(int left, int right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
int main() {
cout << rangeBitwiseAnd(5, 7) << endl; // Output: 4
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Lower bits flip frequently as numbers increase within a range. Since the AND operation requires all bits to be 1 across every number, any bit that changes within the range becomes 0 in the final result. Only the stable prefix bits remain.
Yes, this problem or similar bit manipulation questions are commonly asked in FAANG and other top tech interviews. Interviewers use it to test understanding of bitwise operations, patterns in binary numbers, and optimization techniques.
No special data structure is required for this problem. It primarily relies on bit manipulation operations such as shifting and comparisons. The solution works directly with integers, keeping the space complexity constant.
The optimal approach is to find the common leftmost prefix of the two range boundaries. By right-shifting both numbers until they become equal and then shifting the result back, you effectively remove all differing lower bits. This avoids iterating through every number in the range.
C++ Explanation: This follows a similar logic as the C implementation, leveraging the C++ standard library.