We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

IP to CIDR

Number: 752

Difficulty: Medium

Paid? Yes

Companies: Databricks, Airbnb

Problem Description

Given a starting IP address and a count n, generate the minimum list of CIDR blocks that exactly cover the range of IP addresses from ip to ip + n - 1 without including any addresses outside the range.

Key Insights

  • Convert the IP address from its dotted decimal form to a 32-bit integer.
  • Use bit manipulation to determine the largest block (power of 2) that can start at the current IP without exceeding the remaining count n.
  • Compute the block's prefix length from its size (using log2).
  • Update the starting IP and n after adding each CIDR block until all addresses are covered.

Space and Time Complexity

Time Complexity: O(log n) – The number of iterations scales logarithmically with the number of IPs to cover. Space Complexity: O(1) – Only a constant amount of extra space is used apart from the output list.

Solution

The solution uses a greedy approach. First, the IP is converted into a numerical representation. For each step, the algorithm finds the largest block that can be assigned by taking the lowest one bit from the current IP, which reveals the maximum possible aligned block size. If this block size is larger than the remaining number of IPs needed (n), it is reduced until it fits within n. The prefix length for the block is calculated from the block size. The current IP and remaining number n are then updated, and the process repeats until all IP addresses have been covered.

Code Solutions

def ipToCIDR(ip: str, n: int):
    # Helper function to convert IP string to integer
    def ip_to_int(ip_str):
        parts = list(map(int, ip_str.split(".")))
        return (parts[0] << 24) + (parts[1] << 16) + (parts[2] << 8) + parts[3]
    
    # Helper function to convert integer back to IP string
    def int_to_ip(num):
        return f"{(num >> 24) & 255}.{(num >> 16) & 255}.{(num >> 8) & 255}.{num & 255}"
    
    start = ip_to_int(ip)
    result = []
    while n > 0:
        # Find the lowest set bit, which determines maximum block size based on alignment.
        low_bit = start & -start
        # Adjust the block size if it exceeds the number of IPs remaining.
        while low_bit > n:
            low_bit //= 2
        # Convert block size to prefix length: 32 - log2(block_size)
        prefix = 32 - (low_bit.bit_length() - 1)
        result.append(int_to_ip(start) + "/" + str(prefix))
        start += low_bit
        n -= low_bit
    return result

# Example usage:
print(ipToCIDR("255.0.0.7", 10))
← Back to All Questions