algoadvance

Leetcode 201. Bitwise AND of Numbers Range

Problem Statement

LeetCode Problem 201: Bitwise AND of Numbers Range

Given two integers left and right, return the bitwise AND of all numbers in the inclusive range [left, right].

Clarifying Questions

  1. Input Range: What are the constraints on left and right?
    • Constraint: 0 <= left <= right <= 2^31 - 1
  2. Order of Input: Should we assume left is always less than or equal to right?
    • Yes, it is given that 0 <= left <= right.

Strategy

  1. Observation:
    • When performing bitwise AND on a range of numbers, if we look at their binary representation, the result changes significantly when there is a change in the bit from 0 to 1 or 1 to 0 within the range.
    • The bits that remain the constant 1 across all numbers in the range [left, right] will contribute to the final result.
  2. Common Bit Prefix Strategy:
    • We can solve the problem by aligning left and right such that they share the common prefix of bits.
    • We right-shift both left and right until they are equal because the differing bits beyond the common prefix will yield 0 when ANDed.
  3. Steps:
    • Initialize a shift counter to count the number of right shifts.
    • Right shift both left and right until they become equal.
    • Left shift the result back by the number of shift operations performed.

Code

Here is the C++ code implementing this strategy:

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        // Find the common prefix
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        // Left shift the result back to its original position
        return left << shift;
    }
};

Time Complexity

The time complexity of the algorithm:

The space complexity is ( O(1) ) as we are only using a few extra integer variables for shifting operations.

Explanation

  1. Common Bit Prefix: By right-shifting both left and right until they are the same, we effectively find the common bit prefix.
  2. Left Shift Back: The number of shifts determines how many trailing zeros there are, so we need to left-shift back to get the final result where those trailing bits are zeroed out.

This solution efficiently finds the bitwise AND of all numbers in the given range using bit manipulation.

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