IP to CIDR
Medium · Bit Manipulation · Bit Manipulation · String · Greedy
Problem
An IPv4 address is a 32-bit unsigned number written as four bytes in decimal, joined by dots: the bits 00001010 00000000 00000001 00000011 are written "10.0.1.3".
A CIDR block "base/k" names every address whose first k bits equal the first k bits of base, so it holds exactly 2^(32 - k) addresses. "10.0.1.0/24" is the 256 addresses 10.0.1.0 through 10.0.1.255; "10.0.1.3/32" is that one address.
You are given a starting address ip and a count n. Cover the n consecutive addresses ip, ip + 1, …, ip + n - 1 with as few CIDR blocks as possible, and cover nothing else: a block that reaches even one address outside the range is not allowed.
Return the blocks as strings "a.b.c.d/k", where a.b.c.d is the first address of the block, listed in increasing address order. The shortest cover is unique, so there is exactly one right answer.
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 is 255.0.0.7 to 255.0.0.16. Address 7 is odd, so no block bigger than one address can start there. From 8, a block of 8 (/29, the last byte 00001xxx) fits exactly and ends at 15, and 16 is left over on its own. 255.0.0.0/28 would cover all ten, but it also covers 0 to 6, which are outside the range.
Input: ip = "117.145.102.62", n = 8 Output: ["117.145.102.62/31","117.145.102.64/30","117.145.102.68/31"]
62 is even but not a multiple of 4, so the first block holds 2 addresses (62, 63). 64 could start a block of 64, but only 6 addresses remain, so it takes 4 (64 to 67), and the last 2 (68, 69) form a /31.
Constraints
- ip is a valid IPv4 address "a.b.c.d", each part in [0, 255] with no leading zeros
- 1 <= n <= 1000
- ip + n - 1 <= 255.255.255.255 (the range never wraps past the last address)
Approaches
- Baseline: one /32 per address, merge buddies — time O(n), space O(n)
Follow-up
What if the range is given as two addresses, first and last, and can span billions of addresses? The greedy never looks at individual addresses, so it still makes at most about 62 blocks; the buddy-merge baseline would need one entry per address. IPv6 is the same algorithm on 128-bit numbers.
Related problems
Start free on Cariara · Coding problems · System design studio
