751. IP to CIDR
Asked at Databricks, OpenAI
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
String
Companies
2
Problem
You are given a start IPv4 address ip and a count n. Think of every IPv4 address as a 32-bit number. The addresses you must cover are exactly the n addresses in the inclusive range from ip to ip + n - 1.
A CIDR block is written as base/prefix, where prefix is a number k from 0 to 32. It covers every address whose first k bits equal the first k bits of base. So a block with prefix k always covers exactly 2^(32-k) addresses, and its base must be aligned: the last 32-k bits of the base are all zero.
Return the shortest list of CIDR blocks that covers the range exactly — every address in the range is covered, and no address outside the range is covered. If several shortest lists exist, any one of them is accepted.
Cover 10 addresses with aligned blocks only
Constraints
- ●
7 <= ip.length <= 15 - ●
ip is a valid IPv4 address "a.b.c.d" with each part in [0, 255] - ●
1 <= n <= 1000 - ●
Every implied address ip + x for x < n is a valid IPv4 address
Examples
ip = "255.0.0.7", n = 10["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]ip = "117.145.102.62", n = 8["117.145.102.62/31","117.145.102.64/30","117.145.102.68/31"]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
Key insight: convert the IP to a 32-bit integer. The CIDR block size is determined by the trailing zeros in the binary representation. A block of size 2^k covers IPs from (ip & ~(2^k-1)) to (ip & ~(2^k-1)) + 2^k - 1.
Algorithm: while numIps > 0:
- Convert start IP to integer.
- Find the number of trailing zeros in start (call it tz).
- The maximum block size is 2^tz, but also limited by numIps.
- Find the largest power of 2 <= min(2^tz, numIps). Call it blockSize.
- The CIDR prefix length = 32 - log2(blockSize).
- Add the CIDR block to result.
`- Advance start by blockSize. Decrement numIps by blockSize.
Converting IP to integer: "a.b.c.d" = a2^24 + b2^16 + c*2^8 + d. Use int.from_bytes or manual bit shifting.
Converting integer to IP: shift and mask. (ip >> 24) & 0xFF, (ip >> 16) & 0xFF, etc.
The trailing zeros trick: use ip & (-ip) to isolate the lowest set bit. The block size is the minimum of this value and the remaining IPs. This avoids computing log2 manually.
Edge cases: start IP at the boundary of a block (e.g., 0.0.0.0 with trailing zeros = 32), numIps = 0 (return empty list), numIps larger than remaining block (split into multiple blocks).
Optimal Approach
Convert start IP to a 32-bit integer. While numIps > 0:
- Find the number of trailing zeros in start:
tz = trailingZeros(start). If start is 0, tz = 32. - The maximum block size from trailing zeros is
1 << tz. - The actual block size is the largest power of 2 that fits:
blockSize = min(1 << tz, largestPowerOf2 <= numIps). - Calculate prefix length:
32 - log2(blockSize). - Add
integerToIP(start)/prefixLengthto result. start += blockSize.numIps -= blockSize.
To find the largest power of 2 <= n: use n & (-n) to get the lowest set bit, or use bit_length.
Time: O(numIps) in the worst case (many /32 blocks). Space: O(1) for output.
Greedy: take the biggest aligned block that fits
What Trips People Up in Real Interviews
Forgetting that the block size must be a power of 2. You cannot use arbitrary sizes. The CIDR notation inherently means the block size is 2^(32-prefix). Always round down to the nearest power of 2.
Off-by-one in the prefix calculation. A block of size 2^k has prefix 32-k. So size 1 = /32, size 2 = /31, size 4 = /30, etc. Don't confuse the number of addresses with the prefix length.
Not handling the case where numIps exceeds the remaining block. If the start IP is at the boundary of a /29 block (size 8) but you only need 3 more IPs, use a smaller block that covers exactly 3 IPs (round down to power of 2).
Using floating point for log2 and getting precision errors. Use integer bit operations instead. block.bit_length() - 1 gives log2 for powers of 2. Avoid math.log2 for IP calculations.
Converting IP to integer incorrectly. The formula is a*2^24 + b*2^16 + c*2^8 + d. Don't concatenate the octets as a string and parse as integer.
Solution Code
O(n) timedef ipToCIDR(ip, n):
def ip_to_int(ip):
parts = list(map(int, ip.split('.')))
return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3]
def int_to_ip(num):
return '.'.join(str((num >> (24 - 8 * i)) & 0xFF) for i in range(4))
def trailing_zeros(x):
if x == 0:
return 32
count = 0
while x & 1 == 0:
x >>= 1
count += 1
return count
start = ip_to_int(ip)
result = []
while n > 0:
tz = trailing_zeros(start)
max_block = 1 << tz
block = max_block
while block > n:
block >>= 1
prefix = 32 - (block.bit_length() - 1)
result.append(f"{int_to_ip(start)}/{prefix}")
start += block
n -= block
return resultFrequently Asked Questions
What is the IP to CIDR problem?
Given a start IP address and a number of IPs to cover, return the minimum list of CIDR blocks that exactly covers the range. This tests your understanding of IP addresses, subnet masks, and binary representation.
How do you solve IP to CIDR?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask IP to CIDR?
IP to CIDR is asked at Databricks, OpenAI. It is a medium difficulty problem.
What are common mistakes on IP to CIDR?
- Forgetting that the block size must be a power of 2. You cannot use arbitrary sizes. The CIDR notation inherently means the block size is 2^(32-prefix). Always round down to the nearest power of 2.
- Off-by-one in the prefix calculation. A block of size 2^k has prefix 32-k. So size 1 = /32, size 2 = /31, size 4 = /30, etc. Don't confuse the number of addresses with the prefix length.
- Not handling the case where numIps exceeds the remaining block. If the start IP is at the boundary of a /29 block (size 8) but you only need 3 more IPs, use a smaller block that covers exactly 3 IPs (round down to power of 2).
- Using floating point for log2 and getting precision errors. Use integer bit operations instead. `block.bit_length() - 1` gives log2 for powers of 2. Avoid `math.log2` for IP calculations.
- Converting IP to integer incorrectly. The formula is `a*2^24 + b*2^16 + c*2^8 + d`. Don't concatenate the octets as a string and parse as integer.