Python solution with O(min(log^2 n,log^2 m))


  • 0
    A
    class Solution:
        # @param {integer} m
        # @param {integer} n
        # @return {integer}
    	def rangeBitwiseAnd(self, m, n):
    		if m == n:	return m
    		if m  <= 1 or n <= 1:	return 0
    		powerM = 1
    		while m/powerM > 1:
    			powerM *= 2
    		powerN = 1
    		while n/powerN > 1:
    			powerN *= 2
    		if powerM != powerN:
    			return 0
    		else:
    			return powerM + self.rangeBitwiseAnd(m-powerM, n-powerN)

  • 0

    Isn't that O(min(log n,log m)2)? You're searching for the high bit again and again. O(log) searches, each O(log).


  • 0
    A

    Yes, you are right


Log in to reply
 

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