Bitwise AND of Number Range - LeetCode Daily Challenge

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

Example 2

Input: left = 0, right = 0
Output: 0

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        while(left != right) {
            left = left >> 1;
            right = right >> 1;
            count += 1;
        }

        while(count-- > 0) {
            left = left << 1;
        }

        return left;
    }
}

C++ Code

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            count++;
        }

        while (count-- > 0) {
            left <<= 1;
        }

        return left;
    }
};

Python Code

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        count = 0
        while left != right:
            left >>= 1
            right >>= 1
            count += 1

        while count > 0:
            left <<= 1
            count -= 1

        return left

Javascript Code

var rangeBitwiseAnd = function(left, right) {
    let count = 0;
    while (left !== right) {
        left >>= 1;
        right >>= 1;
        count++;
    }

    while (count-- > 0) {
        left <<= 1;
    }

    return left;
};

Go Code

func rangeBitwiseAnd(left int, right int) int {
    count := 0
    for left != right {
        left >>= 1
        right >>= 1
        count++
    }

    for count > 0 {
        left <<= 1
        count--
    }

    return left
}

Complexity Analysis

Time Complexity: O(1), although there is a loop in the algorithm, the number of iterations is bounded by the number of bits that an integer has, which is fixed.
Space Complexity: O(1), the consumption of the memory for our algorithm is constant, regardless of the input.