LeetCode 751 - IP to CIDR

This problem is asking us to take a starting IPv4 address and a number n of consecutive IP addresses and convert them into the minimal set of CIDR blocks that exactly covers that range. An IPv4 address is a 32-bit number written in the familiar dotted decimal format (e.g., "192.

leetcodemediumstringbit-manipulation

LeetCode Problem 751

Difficulty: 🟡 Medium
Topics: String, Bit Manipulation

Solution

Problem Understanding

This problem is asking us to take a starting IPv4 address and a number n of consecutive IP addresses and convert them into the minimal set of CIDR blocks that exactly covers that range. An IPv4 address is a 32-bit number written in the familiar dotted decimal format (e.g., "192.168.1.1"), where each segment represents 8 bits. A CIDR block, such as "192.168.1.0/24", specifies a range of addresses by fixing the first k bits and allowing the remaining 32 - k bits to vary.

The input consists of a valid IPv4 string ip and an integer n representing the number of consecutive addresses to cover. The output must be a list of CIDR blocks that cover all these addresses, no more and no less. The challenge lies in using the fewest CIDR blocks possible, which often involves combining consecutive addresses into the largest valid block aligned at powers of two.

Constraints tell us the input IP is always valid and 1 <= n <= 1000. Therefore, the range of addresses is relatively small, and we do not need to handle wrap-around at 255.255.255.255. Important edge cases include small ranges (n=1), ranges that are not powers of two, and starting addresses that are not aligned to power-of-two boundaries.

Approaches

The brute-force approach would generate all n IP addresses and attempt to combine them into CIDR blocks in a naïve manner, checking every possible block size at every address. While this would eventually produce the correct result, it is inefficient because it involves iterating over potentially thousands of individual addresses and trying all block sizes, leading to unnecessary computation.

The optimal approach relies on two observations from bit manipulation and binary alignment:

  1. Each CIDR block must start at an address aligned to its block size. For example, a block of size 8 must start at a multiple of 8 in integer form.
  2. The maximum block size at each step is constrained both by the alignment of the current starting IP and the remaining number of addresses to cover. We can compute the largest power-of-two block that fits both constraints.

The algorithm converts the IP to a 32-bit integer, repeatedly calculates the largest valid block to cover the remaining addresses, appends the corresponding CIDR string, and increments the starting IP until all addresses are covered.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * log n) O(n) Generate all IPs, then merge into blocks
Optimal O(log n) O(log n) Uses bit manipulation to greedily choose largest blocks

Algorithm Walkthrough

  1. Convert IP to integer: Transform the starting IP string into a 32-bit integer for easier arithmetic and bitwise operations.

  2. Initialize result list: Prepare a list to store CIDR block strings.

  3. Iterate while addresses remain: While n > 0:

  4. Compute the largest block size allowed by the current IP alignment using x & -x, which isolates the least significant set bit.

  5. Compute the largest block size allowed by the remaining addresses using 2^floor(log2(n)).

  6. Take the minimum of these two to get the block size for the current step.

  7. Convert this block size into CIDR prefix length with 32 - log2(block_size).

  8. Append the CIDR string for the current IP and prefix to the result list.

  9. Increment the IP integer by the block size and decrement n accordingly.

  10. Return the result list after covering all addresses.

Why it works: This greedy algorithm guarantees minimal CIDR blocks because at each step it chooses the largest possible aligned block without exceeding the remaining range. Using powers of two ensures alignment and full coverage.

Python Solution

from typing import List
import math

class Solution:
    def ipToCIDR(self, ip: str, n: int) -> List[str]:
        def ip_to_int(ip_str: str) -> int:
            parts = list(map(int, ip_str.split('.')))
            res = 0
            for part in parts:
                res = res * 256 + part
            return res
        
        def int_to_ip(ip_int: int) -> str:
            return '.'.join(str((ip_int >> (8 * i)) % 256) for i in reversed(range(4)))
        
        res = []
        start = ip_to_int(ip)
        
        while n > 0:
            # Max block size due to IP alignment
            lsb = start & -start
            max_size = 1
            while max_size <= lsb:
                max_size <<= 1
            max_size >>= 1
            
            # Max block size due to remaining addresses
            while max_size > n:
                max_size >>= 1
            
            prefix_len = 32 - int(math.log2(max_size))
            res.append(f"{int_to_ip(start)}/{prefix_len}")
            
            start += max_size
            n -= max_size
        
        return res

Implementation Explanation: The ip_to_int and int_to_ip functions convert between string and integer representations. The lsb calculation uses x & -x to find alignment limits. The loop determines the largest block size allowed by alignment and remaining addresses, computes the corresponding CIDR prefix, updates the start IP, and decrements n.

Go Solution

import (
    "fmt"
    "math"
    "strconv"
    "strings"
)

func ipToCIDR(ip string, n int) []string {
    ipToInt := func(ipStr string) int {
        parts := strings.Split(ipStr, ".")
        res := 0
        for _, part := range parts {
            num, _ := strconv.Atoi(part)
            res = res*256 + num
        }
        return res
    }

    intToIP := func(ipInt int) string {
        parts := make([]string, 4)
        for i := 3; i >= 0; i-- {
            parts[i] = strconv.Itoa(ipInt % 256)
            ipInt /= 256
        }
        return strings.Join(parts, ".")
    }

    res := []string{}
    start := ipToInt(ip)
    
    for n > 0 {
        lsb := start & -start
        maxSize := 1
        for maxSize <= lsb {
            maxSize <<= 1
        }
        maxSize >>= 1

        for maxSize > n {
            maxSize >>= 1
        }

        prefixLen := 32 - int(math.Log2(float64(maxSize)))
        res = append(res, fmt.Sprintf("%s/%d", intToIP(start), prefixLen))

        start += maxSize
        n -= maxSize
    }
    
    return res
}

Go-Specific Notes: Go does not have direct support for math.log2 on integers, so we cast to float64. Slices are used for dynamic lists. Conversion between strings and integers uses strconv.Atoi and strconv.Itoa.

Worked Examples

Example 1: ip = "255.0.0.7", n = 10

  1. Convert IP to integer: start = 4278190095
  2. First iteration: lsb = 1, max block size = 1 → CIDR "255.0.0.7/32", start += 1, n = 9
  3. Second iteration: lsb = 8, max block size = 8 → CIDR "255.0.0.8/29", start += 8, n = 1
  4. Third iteration: max block size = 1 → CIDR "255.0.0.16/32", done

Example 2: ip = "117.145.102.62", n = 8

  1. Convert IP to integer: start = 1977140294
  2. First iteration: lsb = 2 → CIDR "117.145.102.62/31", start += 2, n = 6
  3. Second iteration: lsb = 4 → CIDR "117.145.102.64/30", start += 4, n = 2
  4. Third iteration: lsb = 2 → CIDR "117.145.102.68/31", done

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each iteration covers at least one address and often a power-of-two block, so iterations are proportional to log(n)
Space O(log n) Result list stores at most log(n) CIDR blocks

The reasoning is that each block covers a power-of-two number of addresses, reducing the remaining range exponentially, and conversions are constant time.

Test Cases

sol = Solution()

# Provided examples
assert sol.ipToCIDR("255.0.0.7", 10) == ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]  # minimal covering
assert sol.ipToCIDR("117.145.102.62", 8) == ["117.145.102.62/31","117.145.102.64/30","117.145