Bitwise AND of Numbers Range solution and explanation
Google
9 more videos on this problem
Bitwise AND of numbers range | Range AND query | Leetcode #201Techdose · 12:42 · 41K views
LeetCode Day 23 - Bitwise AND of Numbers RangeErrichto Algorithms · 12:04 · 28K views
Bitwise AND of Numbers Range - Leetcode 201 - PythonNeetCodeIO · 18:25 · 22K views
Bitwise AND of Numbers Range | 2 Approaches | Dry Run | Leetcode 201codestorywithMIK · 34:43 · 11K views
201. Bitwise AND of Numbers Range | Remove Last Set Bit | Bit ManipulationAryan Mittal · 17:10 · 7K views
LeetCode 201 | Bitwise AND of Numbers Range | Solution Explained (Java)Xavier Elon · 7:23 · 1K views
201. Bitwise AND of Numbers RangeXinru Chen · 6:43 · 1K views
Bitwise AND of Numbers Range | bitwise and of numbers range | bitwise and of numbers range leetcodeAkshay Goyal · 4:40 · 1K views
Leetcode | 201. Bitwise AND of Numbers Range | Medium | JavaDeveloper Docs · 9:31 · 666 views
Solving LeetCode 201 Bitwise AND of Numbers Range | Bit Manipulation | Google | Apple | AmazonCode Harmony · 7:47 · 442 views
The problem
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
Approach overview
Problem Overview: Given two integers left and right, compute the bitwise AND of every number in the inclusive range [left, right]. A naive approach would AND each number sequentially, but large ranges make that too slow. The key observation: if any bit position changes within the range, that bit becomes 0 in the final result.
Approach 1: Bit-shift Reduction (O(log n) time, O(1) space)
This approach repeatedly right-shifts both left and right until they become equal. Every shift removes the least significant bit where differences may occur. Each time the values differ, the lower bits must eventually flip within the range, meaning they contribute 0 to the final AND result. Count how many shifts are performed, then left-shift the common value back by that amount to restore the shared prefix.
The insight: the final answer is simply the common binary prefix of left and right. All trailing bits become zero because the range includes numbers where those bits toggle. Since integers have at most 32 bits, the loop runs at most 32 iterations, making the runtime effectively constant. This method relies heavily on bit manipulation operations like >> and <<.
Approach 2: Prefix Matching (O(log n) time, O(1) space)
This method focuses directly on identifying the longest common binary prefix between left and right. Start from the most significant bit and compare positions while both numbers share the same value. Once a mismatch occurs, all remaining bits must be zero in the result because the range includes numbers with both 0 and 1 in those positions.
You can implement this by repeatedly clearing the lowest set bit of right using right = right & (right - 1) until right <= left, or by comparing prefixes through shifts. Both techniques rely on properties of bitwise operators and binary representation. The algorithm runs in at most the number of bits in the integer (around 32 for typical constraints), keeping time complexity logarithmic.
Recommended for interviews: Interviewers typically expect the bit-shift reduction approach. It demonstrates clear understanding of how ranges affect binary bits and avoids unnecessary iteration through the range. A brute-force AND across all numbers shows the basic idea but fails performance constraints for large ranges. Recognizing that the result equals the shared binary prefix shows strong understanding of bit manipulation patterns frequently tested in technical interviews.
Approach 1: Bit-shift Reduction
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.
def rangeBitwiseAnd(left, right):
shift = 0
while left < right:
left >>= 1
right >>= 1
shift += 1
return left << shift
print(rangeBitwiseAnd(5, 7)) # Output: 4public class Main {
public static int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
public static void main(String[] args) {
System.out.println(rangeBitwiseAnd(5, 7)); // Output: 4
}
}#include <iostream>
using namespace std;
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
int main() {
cout << rangeBitwiseAnd(5, 7) << endl; // Output: 4
return 0;
}function rangeBitwiseAnd(left, right) {
let shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
console.log(rangeBitwiseAnd(5, 7)); // Output: 4#include <stdio.h>
int rangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
int main() {
printf("%d\n", rangeBitwiseAnd(5, 7)); // Output: 4
return 0;
}using System;
class MainClass {
public static int RangeBitwiseAnd(int left, int right) {
int shift = 0;
while (left < right) {
left >>= 1;
right >>= 1;
shift++;
}
return left << shift;
}
public static void Main(string[] args) {
Console.WriteLine(RangeBitwiseAnd(5, 7)); // Output: 4
}
}Python Explanation:The Python implementation is concise and leverages Python's ability to handle bit manipulation directly in a while loop.
Time Complexity: O(log N).
Space Complexity: O(1).
Approach 2: Prefix Matching
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.
def rangeBitwiseAnd(left, right):
while left < right:
right &= (right - 1)
return right
print(rangeBitwiseAnd(5, 7)) # Output: 4public class Main {
public static int rangeBitwiseAnd(int left, int right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
public static void main(String[] args) {
System.out.println(rangeBitwiseAnd(5, 7)); // Output: 4
}
}#include <iostream>
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;
}function rangeBitwiseAnd(left, right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
console.log(rangeBitwiseAnd(5, 7)); // Output: 4#include <stdio.h>
int rangeBitwiseAnd(int left, int right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
int main() {
printf("%d\n", rangeBitwiseAnd(5, 7)); // Output: 4
return 0;
}using System;
class MainClass {
public static int RangeBitwiseAnd(int left, int right) {
while (left < right) {
right &= (right - 1);
}
return right;
}
public static void Main(string[] args) {
Console.WriteLine(RangeBitwiseAnd(5, 7)); // Output: 4
}
}Python Explanation: Python's logical operations make it straightforward to implement this method.
Time Complexity: O(log N).
Space Complexity: O(1).
Approach 3: Default Approach
func rangeBitwiseAnd(left int, right int) int {
for left < right {
right &= (right - 1)
}
return right
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit-shift Reduction | Time Complexity: O(log N). |
| Prefix Matching | Time Complexity: O(log N). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit-shift Reduction | O(log n) | O(1) | Best general solution. Quickly finds the common binary prefix by shifting both numbers. |
| Prefix Matching / Bit Clearing | O(log n) | O(1) | Useful when leveraging bit tricks like clearing the lowest set bit of the upper bound. |
Frequently asked questions
Is Bitwise AND of Numbers Range easy or hard?
The problem is classified as Medium because the brute-force idea is simple but inefficient. The challenge lies in recognizing that only the common binary prefix of the range contributes to the final result, which requires understanding bit manipulation patterns.
Bitwise AND of Numbers Range Python/Java solution
Most implementations use a loop that right-shifts both left and right until they become equal, counting the shifts. Afterward, the result is reconstructed with a left shift. This logic is identical across Python, Java, C++, C#, and JavaScript because it relies on standard bitwise operators.
How to solve Bitwise AND of Numbers Range in O(n)?
A straightforward approach iterates from left to right and continuously applies the AND operator: result &= current_number. This works but can be extremely slow when the range is large. Optimized solutions avoid iteration by analyzing binary prefixes instead.
What is the best approach for Bitwise AND of Numbers Range?
The optimal approach finds the common binary prefix between left and right. The common implementation repeatedly right-shifts both numbers until they match, then restores the prefix with left shifts. This runs in O(log n) time where n is the maximum value of the range and uses O(1) space.
Is Bitwise AND of Numbers Range asked at Google/Amazon/Meta?
Bit manipulation range problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of binary representation and recognizing patterns where brute force can be replaced with bit-level reasoning.
What data structure is used in Bitwise AND of Numbers Range?
No special data structure is required. The solution relies on bit manipulation operations such as shifting and masking to analyze the binary representation of integers. The algorithm operates directly on primitive integer values.
What is the time complexity of Bitwise AND of Numbers Range?
The optimal solution runs in O(log n) time because it processes at most the number of bits in the integers (typically 32). Each iteration removes one differing bit until both numbers share the same prefix. Space complexity remains O(1).