NeetCode #880LC-751MediumBit Manipulation
← Back to All Problems#880 · #751 · IP to CIDR(IP 到 CIDR)
📌 Problem Statement & Constraints
Given a start IPv4 address
ip and an integer n, return the smallest list of CIDR blocks that together cover every address from ip through ip + n - 1. Constraints: ip is a valid IPv4 address and 1 <= n <= 1000.💡 Core Algorithmic Approaches
- Convert the IPv4 address to a 32-bit integer, then cover the range greedily with the largest aligned blocks.
- The largest block starting at address
ais capped by the number of trailing zeros ofa(its alignment) and by the remaining count. - A block of size
2^kcovers2^kaddresses and is written with prefix length32 - k. - Emit the block, advance the address by its size, and repeat until
naddresses have been covered.
💻 Benchmark Python3 Implementation
class Solution:
def ipToCIDR(self, ip: str, n: int) -> List[str]:
def to_int(s: str) -> int:
a, b, c, d = map(int, s.split("."))
return (a << 24) | (b << 16) | (c << 8) | d
def to_ip(x: int) -> str:
return ".".join(str((x >> shift) & 255) for shift in (24, 16, 8, 0))
start = to_int(ip)
res = []
while n > 0:
# alignment: the largest power of two that divides start
lowbit = start & (-start) if start else (1 << 32)
size = 1
while size * 2 <= n and size * 2 <= lowbit:
size *= 2
prefix = 32 - (size.bit_length() - 1)
res.append(to_ip(start) + "/" + str(prefix))
start += size
n -= size
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n): a handful of blocks, each handled in constant time.
💾 Space Complexity
O(1) beyond the output list.
⚠️ Interview Pitfalls & Follow-ups
- Choosing a fixed block size: the block must respect both the address alignment and the remaining count.
- Off-by-one in the prefix length: a block of size
2^khas prefix length32 - k, so size 1 gives /32 and size 8 gives /29. - Ignoring alignment: a block of size
2^kmust start at a multiple of2^k, which is why the size is capped by the low bit. - Crashing on the address
0.0.0.0:start & -startis 0 there, so the alignment cap needs a guard.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.