Bitwise And Of A Range

Mark as Completed

Lesson

Given two non-negative integers X and Y, where X is less than or equal to Y, find the bitwise AND of all the integers in the range from X to Y, inclusive. Implement a function findBitwiseAndRange(X, Y)
to solve this problem.

Example:

Input: X = 2, Y = 4
Output: 0

Explanation: In binary representation, 2 is 10, 3 is 11, and 4 is 100. Performing bitwise AND on 2 and 3 results in 2, and bitwise AND on 2 and 4 results in 0.

Walkthrough

The problem requires us to find the bitwise AND of all the integers in the range from X to Y, inclusive. One way to solve this problem is to keep right-shifting both X and Y until they are equal, counting the number of times we had to shift. The reason we do this is because until they are equal, the bits that are lost in the right shift will ultimately yield a 0 bit on the AND operation anyways. Once they are equal, we left-shift X by the count number of times and return the result.

To implement this solution, we will create a function findBitwiseAndRange(X, Y)
that takes two non-negative integers X and Y. We will first initialize a counter variable count
to zero. We will then loop while X is not equal to Y and perform right-shifting on X and Y. We will then increase count
by one each time we perform the shift. After the loop, we will left-shift X by the count
number of times and return the result.

function findBitwiseAndRange(X, Y) {
  let count = 0;
  while (X !== Y) {
    X >>= 1;
    Y >>= 1;
    count++;
  }
  return X << count;
}

Big O Complexity Analysis:

The time complexity of this solution is O(log n), where n is the value of the larger number between X and Y. This is because we perform a right-shift on X and Y, halving their value, in every iteration of the loop until X and Y are equal. This reduces the time complexity significantly. The space complexity of this solution is O(1), as we are only using a constant amount of memory to store the counter variable count
.

Previous Lesson Next Lesson