5 lines of Python, O(logn) time

  • 0
    class Solution(object):
        def rangeBitwiseAnd(self, m, n):
            j = -1
            for i in range(31, -1, -1):
                if (m >> i) != (n >> i):
                    j = i; break
            return (m >> (j+1)) * (1 << (j+1))

  • 0

    I don't think your code runs in O(log n) time. Because when we talk about the complexity of algorithms, n means "size" of input, NOT "value" of input. As for this problem, the input size is number of bits in the integer, not value of input n.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.