201. Bitwise AND of Numbers Range - Explanation

Description

You are 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 = 1, right = 5

Output: 0

Example 2:

Input: left = 10, right = 12

Output: 8

Constraints:

0 <= left <= right <= ((2^31)-1)

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        res = left
        for i in range(left + 1, right + 1):
            res &= i
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

2. Bit Manipulation - I

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        res = 0
        for i in range(32):
            bit = (left >> i) & 1
            if not bit:
                continue

            remain = left % (1 << (i + 1))
            diff = (1 << (i + 1)) - remain
            if right - left < diff:
                res |= (1 << i)

        return res

Time & Space Complexity

Time complexity: $O(1)$ since we iterate $32$ times.
Space complexity: $O(1)$

3. Bit Manipulation - II

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

4. Bit Manipulation - III

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right &= right - 1
        return right

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$