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:

"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

Example function shape:

def ipToCIDR(ip: str, n: int) -> list[str]:
    ...

Examples

Input:

ip = "255.0.0.7"
n = 10

Output:

["255.0.0.7/32", "255.0.0.8/29", "255.0.0.16/32"]

The range starts at:

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:

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:

255.0.0.8/29

Now one address remains: 255.0.0.16.

So we emit:

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:

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.

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:

255.0.0.7

can be interpreted as four 8-bit groups:

255   0   0   7

To convert it into an integer:

value = 255 << 24
value += 0 << 16
value += 0 << 8
value += 7

More generally:

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.

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:

x & -x

returns the largest power-of-two block size aligned at x.

For example:

But this aligned block may be larger than the number of addresses remaining.

So we shrink it until it fits:

block = x & -x

while block > n:
    block //= 2

Then block is the largest block we can safely use now.

The CIDR prefix length is:

prefix = 32 - log2(block)

In Python, since block is a power of two:

prefix = 32 - (block.bit_length() - 1)

Examples:

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

The conversion between IP string and integer is constant time because an IPv4 address always has four parts.

Implementation

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.

value = value * 256 + int(part)

Each IPv4 group has 8 bits, which means each group is base 256.

So "255.0.0.7" becomes:

255 * 256^3 + 0 * 256^2 + 0 * 256 + 7

The helper function int_to_ip reverses the process.

(x >> shift) & 255

This extracts one 8-bit group from the integer.

The main loop continues until all n addresses are covered.

block = x & -x

This finds the largest aligned block size at the current address.

Then:

while block > n:
    block //= 2

shrinks the block so we do not cover too many addresses.

The prefix is computed from the block size:

prefix = 32 - (block.bit_length() - 1)

For example, if block = 8, then block.bit_length() - 1 = 3, so the prefix is:

32 - 3 = 29

That gives /29, which covers 8 addresses.

Finally, we append the CIDR block and move forward:

x += block
n -= block

Testing

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: