Show problems as
Classic problem #751MediumStringBit Manipulation

IP to CIDR

Real-world version: Covering an Address Run with Blocks
Tracked in this browser only
Read IP to CIDR on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics