Leetcode 0201 Bitwise AND of Numbers Range

Problem statement

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Solution

The key observation here is that if binary length of numbers is different, then the answer is equal to zero. If lengths are equal, we remove the first symbol (which is “1”) and do recursion. Basically, for two binary numbers a1...an and b1...bn the answer will be the common prefix and the rest are zeros.

Complexity

It is O(log n) for time and space.

Code

class Solution:
    def rangeBitwiseAnd(self, m, n):
        if n == m or m == 0:
            return m
        elif len(bin(m)) != len(bin(n)):
            return 0
        else:
            pref = 1<<(len(bin(m))-3)
            return pref ^ self.rangeBitwiseAnd(m - pref, n - pref)