<reponame>yennanliu/Python_basics<filename>leetcode_python/String/ip-to-cidr.py
# V0 

# V1 
# https://zhuanlan.zhihu.com/p/35541808
# DEV 


# V2 
# Time:  O(n)
# Space: O(1)
class Solution(object):
    def ipToCIDR(self, ip, n):
        """
        :type ip: str
        :type n: int
        :rtype: List[str]
        """
        def ipToInt(ip):
            result = 0
            for i in ip.split('.'):
                result = 256 * result + int(i)
            return result

        def intToIP(n):
            return ".".join(str((n >> i) % 256) \
                            for i in (24, 16, 8, 0))

        start = ipToInt(ip)
        result = []
        while n:
            mask = max(33-(start & ~(start-1)).bit_length(), \
                       33-n.bit_length())
            result.append(intToIP(start) + '/' + str(mask))
            start += 1 << (32-mask)
            n -= 1 << (32-mask)
        return result
# V0 

# V1 
# https://zhuanlan.zhihu.com/p/35541808
# DEV 


# V2 
# Time:  O(n)
# Space: O(1)
class Solution(object):
    def ipToCIDR(self, ip, n):
        """
        :type ip: str
        :type n: int
        :rtype: List[str]
        """
        def ipToInt(ip):
            result = 0
            for i in ip.split('.'):
                result = 256 * result + int(i)
            return result

        def intToIP(n):
            return ".".join(str((n >> i) % 256) \
                            for i in (24, 16, 8, 0))

        start = ipToInt(ip)
        result = []
        while n:
            mask = max(33-(start & ~(start-1)).bit_length(), \
                       33-n.bit_length())
            result.append(intToIP(start) + '/' + str(mask))
            start += 1 << (32-mask)
            n -= 1 << (32-mask)
        return result
# V0 # V1 # https://zhuanlan.zhihu.com/p/35541808 # DEV # V2 # Time:  O(n) # Space: O(1) :type ip: str         :type n: int         :rtype: List[str]