Sponsored
Sponsored
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.
1public class Main {
2 public static int rangeBitwiseAnd(int left, int right) {
3 int shift = 0;
4 while (left < right) {
5 left >>= 1;
6 right >>= 1;
7 shift++;
8 }
9 return left << shift;
10 }
11
12 public static void main(String[] args) {
13 System.out.println(rangeBitwiseAnd(5, 7)); // Output: 4
14 }
15}Java Explanation:In Java, this logic is implemented inside a class with a static method and uses a simple print statement to display the result.
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).
1
C Explanation: This approach applies bitwise operations to continuously zero out the lowest bit of right until left and right become equal.