# LeetCode 751: IP to CIDR ## Problem Restatement We are given a starting IPv4 address `ip` and an integer `n`. We need to cover exactly `n` consecutive IP addresses starting from `ip`. The answer should be a list of CIDR blocks with the smallest possible length. A CIDR block looks like this: ```python "123.45.67.89/20" ``` The number after `/` is the prefix length. A larger prefix length means a smaller block. For example, `/32` covers exactly one IP address, while `/29` covers `8` addresses. The task is to split the range into the fewest valid CIDR blocks. ## Input and Output | Item | Meaning | |---|---| | Input | A valid IPv4 address `ip` and an integer `n` | | Output | A list of CIDR block strings | | Coverage | The blocks must cover exactly `n` consecutive addresses | | Requirement | Use the smallest possible number of CIDR blocks | Example function shape: ```python def ipToCIDR(ip: str, n: int) -> list[str]: ... ``` ## Examples Input: ```python ip = "255.0.0.7" n = 10 ``` Output: ```python ["255.0.0.7/32", "255.0.0.8/29", "255.0.0.16/32"] ``` The range starts at: ```text 255.0.0.7 ``` We need to cover 10 addresses. The first address, `255.0.0.7`, cannot form a larger aligned CIDR block because it ends in binary `...0111`. It is only aligned for a block of size `1`, so we emit: ```text 255.0.0.7/32 ``` Now we move to `255.0.0.8`. The address `255.0.0.8` ends in binary `...1000`, so it is aligned for a block of size `8`. We still need to cover `9` addresses, so we can take all `8`: ```text 255.0.0.8/29 ``` Now one address remains: `255.0.0.16`. So we emit: ```text 255.0.0.16/32 ``` ## First Thought: Generate Every IP One simple idea is to generate all `n` IP addresses one by one. For example, for `255.0.0.7` and `n = 10`, we could generate: ```text 255.0.0.7 255.0.0.8 255.0.0.9 ... 255.0.0.16 ``` This covers the range, but it does not produce CIDR blocks. The output would be too long because each single address would become a `/32` block. That is valid but not shortest. ## Key Insight A CIDR block always covers a power-of-two number of addresses. | CIDR Prefix | Block Size | |---|---| | `/32` | `1` | | `/31` | `2` | | `/30` | `4` | | `/29` | `8` | | `/28` | `16` | So the problem becomes: At the current IP address, choose the largest power-of-two block that: 1. starts exactly at the current address 2. does not pass beyond the remaining `n` addresses The first rule is an alignment rule. For example, an address ending in binary `...1000` is divisible by `8`, so it can start a block of size `8`. An address ending in binary `...0111` is not divisible by `2`, `4`, or `8`, so it can only start a block of size `1`. This is why bit manipulation is useful. ## Convert IP to Integer IPv4 addresses are 32-bit unsigned integers. For example: ```text 255.0.0.7 ``` can be interpreted as four 8-bit groups: ```text 255 0 0 7 ``` To convert it into an integer: ```python value = 255 << 24 value += 0 << 16 value += 0 << 8 value += 7 ``` More generally: ```python def ip_to_int(ip: str) -> int: value = 0 for part in ip.split("."): value = value * 256 + int(part) return value ``` This gives us a number that can be incremented directly to move to the next IP address. ## Convert Integer Back to IP To convert a 32-bit integer back to IPv4 format, extract each 8-bit group. ```python def int_to_ip(x: int) -> str: return ".".join(str((x >> shift) & 255) for shift in (24, 16, 8, 0)) ``` The mask `255` keeps only the lowest 8 bits after shifting. ## Finding the Largest Valid Block At a current integer address `x`, the expression: ```python x & -x ``` returns the largest power-of-two block size aligned at `x`. For example: | Binary Ending | `x & -x` | Meaning | |---|---:|---| | `...0111` | `1` | Only block size `1` is aligned | | `...1000` | `8` | Block sizes up to `8` are aligned | | `...0000` | `16` or more | Larger blocks may be aligned | But this aligned block may be larger than the number of addresses remaining. So we shrink it until it fits: ```python block = x & -x while block > n: block //= 2 ``` Then `block` is the largest block we can safely use now. The CIDR prefix length is: ```python prefix = 32 - log2(block) ``` In Python, since `block` is a power of two: ```python prefix = 32 - (block.bit_length() - 1) ``` Examples: | Block Size | Prefix | |---:|---:| | `1` | `32` | | `2` | `31` | | `4` | `30` | | `8` | `29` | | `16` | `28` | ## Algorithm 1. Convert the starting IP address into a 32-bit integer. 2. Create an empty answer list. 3. While `n > 0`: 1. Find the largest aligned block using `x & -x`. 2. Shrink the block while it is larger than `n`. 3. Convert the current integer address back to IP format. 4. Append `ip/prefix` to the answer. 5. Move `x` forward by `block`. 6. Decrease `n` by `block`. 4. Return the answer. ## Correctness At every step, the algorithm emits a CIDR block starting at the current first uncovered IP address. The value `x & -x` gives the largest power-of-two block that is aligned at `x`. Therefore, any larger block would start before `x` or include addresses before the current uncovered range. If that aligned block is larger than the number of remaining addresses, the algorithm repeatedly halves it until it fits inside the remaining range. Since CIDR block sizes are powers of two, the resulting block is still a valid CIDR block. So each emitted block is valid and covers only uncovered addresses inside the target range. The algorithm then moves `x` forward by exactly the number of addresses covered by that block and subtracts the same amount from `n`. Therefore, no address is skipped and no address is covered twice. Because each step chooses the largest valid CIDR block starting at the current address, no shorter block list can replace that first choice. After choosing it, the same argument applies to the remaining suffix of the range. Thus the greedy method produces the smallest possible list. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(k)` | `k` is the number of CIDR blocks returned | | Space | `O(k)` | The answer list stores `k` blocks | The conversion between IP string and integer is constant time because an IPv4 address always has four parts. ## Implementation ```python class Solution: def ipToCIDR(self, ip: str, n: int) -> list[str]: def ip_to_int(ip: str) -> int: value = 0 for part in ip.split("."): value = value * 256 + int(part) return value def int_to_ip(x: int) -> str: return ".".join(str((x >> shift) & 255) for shift in (24, 16, 8, 0)) x = ip_to_int(ip) ans = [] while n > 0: block = x & -x while block > n: block //= 2 prefix = 32 - (block.bit_length() - 1) ans.append(f"{int_to_ip(x)}/{prefix}") x += block n -= block return ans ``` ## Code Explanation The helper function `ip_to_int` converts an IPv4 string into a 32-bit integer. ```python value = value * 256 + int(part) ``` Each IPv4 group has 8 bits, which means each group is base `256`. So `"255.0.0.7"` becomes: ```text 255 * 256^3 + 0 * 256^2 + 0 * 256 + 7 ``` The helper function `int_to_ip` reverses the process. ```python (x >> shift) & 255 ``` This extracts one 8-bit group from the integer. The main loop continues until all `n` addresses are covered. ```python block = x & -x ``` This finds the largest aligned block size at the current address. Then: ```python while block > n: block //= 2 ``` shrinks the block so we do not cover too many addresses. The prefix is computed from the block size: ```python prefix = 32 - (block.bit_length() - 1) ``` For example, if `block = 8`, then `block.bit_length() - 1 = 3`, so the prefix is: ```text 32 - 3 = 29 ``` That gives `/29`, which covers `8` addresses. Finally, we append the CIDR block and move forward: ```python x += block n -= block ``` ## Testing ```python def run_tests(): s = Solution() assert s.ipToCIDR("255.0.0.7", 10) == [ "255.0.0.7/32", "255.0.0.8/29", "255.0.0.16/32", ] assert s.ipToCIDR("0.0.0.0", 1) == [ "0.0.0.0/32", ] assert s.ipToCIDR("0.0.0.0", 2) == [ "0.0.0.0/31", ] assert s.ipToCIDR("0.0.0.1", 1) == [ "0.0.0.1/32", ] assert s.ipToCIDR("0.0.0.8", 8) == [ "0.0.0.8/29", ] assert s.ipToCIDR("0.0.0.7", 2) == [ "0.0.0.7/32", "0.0.0.8/32", ] print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `"255.0.0.7", 10` | Matches the main example | | `"0.0.0.0", 1` | Single address becomes `/32` | | `"0.0.0.0", 2` | Aligned block of size `2` becomes `/31` | | `"0.0.0.1", 1` | Unaligned single address | | `"0.0.0.8", 8` | Perfectly aligned block of size `8` | | `"0.0.0.7", 2` | Cannot use `/31` because start address is unaligned |