Python Solution with Analysis (55ms)


  • 0
    L

    First, let me explain the prefix length mentioned in the problem.
    Take the the CIDR block "255.0.0.8/29" as an example.
    255.0.0.8 -> 11111111 00000000 00000000 00001000
    The prefix length 29 means that the first 29 digits are fixed, in other words, the last 3 digits can be changed.
    Because 2^3 = 8, this CIDR block contains 8 IP addresses.
    And these addresses with common prefix of 29 bits are:
    11111111 00000000 00000000 00001000
    11111111 00000000 00000000 00001001
    11111111 00000000 00000000 00001010
    11111111 00000000 00000000 00001011
    11111111 00000000 00000000 00001100
    11111111 00000000 00000000 00001101
    11111111 00000000 00000000 00001110
    11111111 00000000 00000000 00001111

    Second, I am going to talk about my analysis of this problem.
    In essence, the problem needs us to reach a final number by add some powers of 2 to a given number.
    Call the given number StartNum.
    Call the final number EndNum.

    The process is like this:
    StartNum + 2^x0 = Number1
    Number1 + 2^x1 = Number2
    Number2 + 2^x2 = Number3
    Number3 + 2^x3 = Number4
    ...
    NumberN + 2^xN = EndNum

    Let's see an example.
    Input: ip = "255.0.0.7", n = 30
    Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/28","255.0.0.32/30","255.0.0.36/32"]
    StartNum = 7.
    EndNum = 7+30 = 37
    7 + 2^(32-32) = 8
    8 + 2^(32-29) = 16
    16 + 2^(32-28) = 32
    32 + 2^(32-30) = 36
    36 + 2^(32-32) = 37

    Analyze the process in binary format.
    000111 -> 001000
    001000 -> 010000
    010000 -> 100000
    100000 -> 100100
    100100 -> 100101

    Adjust a little.
    000111 -> 000111 (0 free digits)
    001000 -> 001111 (3 free digits)
    010000 -> 011111 (4 free digits)
    100000 -> 100011 (2 free digits)
    100100 -> 100100 (0 free digits)

    The rest thought process is basically the algorithm of the problem. Please just read my codes and think yourself.

    (English is not my nature language. Please forgive me if my explanation is not clear to you.)

    class Solution(object):
        def IpStringtoNumber(self, ip):
            numbers = list(map(int, ip.split(".")))
            n = (numbers[0]<<24) + (numbers[1]<<16) + (numbers[2]<<8) + numbers[3]
            return n
        def NumbertoIpString(self, n):
            return ".".join([str(n>>24&255), str(n>>16&255),str(n>>8&255), str(n&255)])
    
        def ipToCIDR(self, ip, n):
            """
            :type ip: str
            :type n: int
            :rtype: List[str]
            """
            startnum = self.IpStringtoNumber(ip)
            endnum = startnum + n - 1
            currentnum = startnum
            ans = []
            while currentnum <= endnum:
                MaxFreePositions = 0
                while currentnum % (1 << (MaxFreePositions+1)) == 0:
                    MaxFreePositions += 1
                FreePositions = MaxFreePositions
                while (currentnum | ((1 << FreePositions) - 1)) > endnum:
                    FreePositions -=1
                ans.append(self.NumbertoIpString(currentnum) + "/" + str(32-FreePositions))
                currentnum = (currentnum | ((1 << FreePositions) - 1)) + 1
            return ans
    
    

  • 0
    I

    Awesome!!!

    Best Wang!


Log in to reply
 

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