Python Solution (108 ms)


  • 0
    S
    import math
    import functools
    import operator
    class Solution(object):
        def rangeBitwiseAnd(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            if m == 0:
                return 0
            
            if m == n:
                return n
            
            if int(math.log(m,2)) < int(math.log(n,2)):
                return 0
            
            return functools.reduce(operator.and_, range(m,n+1))
    

    Explanation:

    1.m==0

    Anything ANDed with 0 is always 0.

    2.m==n

    If the first and last number are the same, any number ANDed with itself is always itself.

    1. int(math.log(m,2)) < int(math.log(n,2))

    The number of digits in a binary number is int(math.log(DECIMAL_NUMBER,2)) + 1. If the starting number, m, has less digits in its binary representation than ending number, n, does, that means that somewhere in that range there exists a number with a binary representation with 1 followed by int(math.log(NUMBER,2)) number of 0's, and m will be some number starting with 0 and followed by int(math.log(NUMBER,2)) digits

    e.g. With (m=5, n=9), 5=="0101", 6=="0110", 7=="0111", 8=="1000", 5&6&7&8 == 0.

    1. return functools.reduce(operator.and_, range(m,n+1))

    If the integer range has passed all previous checks, return the AND of all the numbers.


Log in to reply
 

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