⚡Flashcard Drill➔
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

  1. Convert the IPv4 address to a 32-bit integer, then cover the range greedily with the largest aligned blocks.
  2. The largest block starting at address a is capped by the number of trailing zeros of a (its alignment) and by the remaining count.
  3. A block of size 2^k covers 2^k addresses and is written with prefix length 32 - k.
  4. Emit the block, advance the address by its size, and repeat until n addresses 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^k has prefix length 32 - k, so size 1 gives /32 and size 8 gives /29.
  • Ignoring alignment: a block of size 2^k must start at a multiple of 2^k, which is why the size is capped by the low bit.
  • Crashing on the address 0.0.0.0: start & -start is 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems