algoadvance

Leetcode 201. Bitwise AND of Numbers Range

Problem Statement

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

  2. Input: left = 0, right = 1 Output: 0

Clarifying Questions

  1. Will the integers always be non-negative?
    • Yes.
  2. Can the range be very large?
    • Yes, the range can be large, so efficiency is important.
  3. What are the constraints?
    • (0 \leq left \leq right \leq 2^{31} - 1)

Strategy

  1. Understanding the Problem:
    • To find the bitwise AND of all numbers between left and right, one approach could be to perform the bitwise AND operation iteratively on each number in the range. However, this might be inefficient for large ranges.
  2. Efficient Approach:
    • Observe that common bits in the result must be the same for all numbers in the range.
    • As numbers increase in a range, lower bits will eventually cycle through 0 and 1, and only the higher, unchanging bits will remain stable after ANDing.
    • We can find the common high bits of left and right by shifting both to the right until they are equal. The remaining bits after shifting left back to the original places will form the result.
  3. Steps to Implement:
    • Initialize two variables left and right.
    • While left is not equal to right, right shift both left and right until they are equal.
    • Count the number of shifts, which gives us how many bits we have to ‘zero out’.
    • Left shift the new value of left back to its position to get the result.

Code

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        // Count the number of shifts
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        // Shift the result back to its original position
        return left << shift;
    }
}

Time Complexity

Explanation

  1. left and right are right-shifted until they become equal:
    • This effectively eliminates bits that differ between left and right.
  2. The variable shift counts how many bits have been shifted out.
  3. Finally, the left variable is left-shifted back to its original position to form the correct result.

This method ensures that we perform the necessary bitwise operations efficiently without having to AND every number in the range.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI