# Python Solution with Analysis (55ms)

• 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

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

``````

• Awesome!!!

Best Wang!

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