Bitwise AND of Numbers Range Python Solution

Tested Python solution for LeetCode 201 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 201, Medium. Topics: Bit Manipulation. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 201   # by problem number
lcpy gen -s bitwise_and_of_numbers_range   # by problem name

​

Problem

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

​

Examples

Input: left = 5, right = 7
Output: 4

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

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

​

Constraints

• 0 <= left <= right <= 2^31 - 1

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(log n) where n is the value of right (number of bits)
    # Space: O(1)
    def range_bitwise_and(self, left: int, right: int) -> int:
        # The AND of the range equals the common most-significant bit prefix
        shift = 0

        while left < right:
            left >>= 1
            right >>= 1
            shift += 1

        return left << shift

​

Complexity

Time	Space
O(log n) where n is the value of right (number of bits)	O(1)

​

Tags

NeetCode 250, NeetCode All.