0617MediumStringBit Manipulation

Covering an Address Run with Blocks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An allocation covers a run of n addresses. The run starts at the IPv4 address ip, written as four decimal pieces separated by dots, and carries on through the next n - 1 addresses in numeric order. An IPv4 address is read as a 32-bit number, the first piece supplying the highest eight bits.

A block is written as an address followed by a slash and a length, for example "10.0.0.8/29". A block written with length p stands for the 2^(32 - p) addresses that agree with the written address in their top p bits, and the written address must have all of its lowest 32 - p bits clear, so the written address is the first address of the block. The length satisfies 1 <= p <= 32.

Cover the run with blocks, working from its first address to its last. At each step, look at the first address not covered yet and pick the block that starts exactly there, stays inside the run, and holds as many addresses as those two conditions allow. Return the blocks in the order they were picked. Every block must lie inside the run, and together they must cover the run exactly.

Examples

Example 1

Input: ip = "10.0.0.6", n = 6
Output: ["10.0.0.6/31", "10.0.0.8/30"]

The first address ends in 6, so a block starting there can hold at most two addresses; `"10.0.0.6/31"` covers 10.0.0.6 and 10.0.0.7. Four addresses are left and the next uncovered address ends in 8, so `"10.0.0.8/30"` covers 10.0.0.8 through 10.0.0.11 and finishes the run.

Example 2

Input: ip = "10.0.0.0", n = 8
Output: ["10.0.0.0/29"]

A single block of eight addresses starts at 10.0.0.0 and ends at 10.0.0.7, and eight addresses means a length of 29 because 32 - 29 = 3 and two to the third power is eight.

Example 3

Input: ip = "10.0.0.7", n = 1
Output: ["10.0.0.7/32"]

Only one address has to be covered, and a length of 32 stands for a single address.

Constraints

7 <= ip.length <= 15
ip is a valid IPv4 address of the form "a.b.c.d" where a, b, c and d are integers in the range [0, 255].
1 <= n <= 1000
Every address in the run is a valid IPv4 address.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

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

Java

public List<String> ipToCIDR(String ip, int n)

The intended approach

Time O(b + log n) per block, where b is the number of blocks returned; at most 32 halvings happen per block.Space O(b) for the returned list of blocks.

The four dotted pieces are folded into one 32-bit number, after which the two conditions on a block become arithmetic. A block that starts at a given address can hold at most as many addresses as the value of that address's lowest set bit, because every lower bit has to be clear inside the written address; and it can hold at most the number of addresses still to cover. The code takes the smaller of the two and halves it until it is no larger than what is left, which keeps it a power of two. The length written after the slash is 32 minus the base-two logarithm of that size. The start then advances by the size and the loop repeats.

Pythonentry point: ip_to_c_i_d_r

def _dotted(value):
    return "%d.%d.%d.%d" % ((value >> 24) & 255, (value >> 16) & 255,
                            (value >> 8) & 255, value & 255)


def ip_to_c_i_d_r(ip, n):
    # O(number of blocks) time, O(number of blocks) space for the answer, and
    # each block costs a constant amount of work. Turning the address into a
    # 32-bit number makes both limits on a block visible: its lowest set bit is
    # the largest block that can start there, and the count still to cover is
    # the largest block that fits. Take the smaller of the two, rounded down to
    # a power of two.
    start = 0
    for piece in ip.split("."):
        start = start * 256 + int(piece)
    blocks = []
    remaining = n
    while remaining > 0:
        alignment = (start & -start) if start else (1 << 32)
        size = alignment
        while size > remaining:
            size >>= 1
        blocks.append(_dotted(start) + "/" + str(33 - size.bit_length()))
        start += size
        remaining -= size
    return blocks

The obvious version

Keep a running position as a plain integer. At each step scan the lengths from 1 upwards, which visits block sizes from largest to smallest, and stop at the first length whose size divides the current position and is no bigger than the count still to cover. Record that block, advance the position by its size, and repeat.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_ip_to_c_i_d_r(ip, n):
    pieces = [int(p) for p in ip.split(".")]
    start = pieces[0] * 16777216 + pieces[1] * 65536 + pieces[2] * 256 + pieces[3]
    remaining = n
    blocks = []
    while remaining > 0:
        for prefix in range(1, 33):
            size = 1 << (32 - prefix)
            if size <= remaining and start % size == 0:
                break
        text = "%d.%d.%d.%d" % (start // 16777216 % 256, start // 65536 % 256,
                                start // 256 % 256, start % 256)
        blocks.append(text + "/" + str(prefix))
        start += size
        remaining -= size
    return blocks

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in