Ctrl K

Fewest Address Blocks

Medium
An IPv4 address is an unsigned 32-bit number written as four decimal bytes separated by dots, such as "10.0.0.6". An address block is written as "address/k" with k from 0 to 32. It covers every address whose first k bits match the first k bits of the given address, which is exactly 2^(32-k) addresses. For example, "10.0.0.8/30" covers 10.0.0.8 through 10.0.0.11. While setting up a firewall, you need to open exactly count consecutive addresses starting at first_ip, no more and no fewer. Use as few blocks as possible and return them. No block may reach outside the range, and blocks must not overlap. In each entry the address is the lowest address of its block. The blocks may be returned in any order.
Example 1
first_ip='10.0.0.6', count=6 → ['10.0.0.6/31', '10.0.0.8/30']

The addresses 10.0.0.6 to 10.0.0.11 are needed. A /31 block covers .6 and .7, a /30 block covers .8 to .11. Fewer than two blocks is impossible.

Example 2
first_ip='192.168.0.0', count=256 → ['192.168.0.0/24']

The start is aligned and the count is a power of two, so a single /24 block is enough.

Example 3
first_ip='172.16.5.255', count=3 → ['172.16.5.255/32', '172.16.6.0/31']
Constraints
  • first_ip is a valid IPv4 address "a.b.c.d" with 0 ≤ a, b, c, d ≤ 255 and no leading zeros
  • 1 ≤ count ≤ 2²⁰
  • The whole range exists: first_ip + count - 1 does not go past 255.255.255.255
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsRecurring Gene Windows MediumWords With No Shared Letters MediumEvery Shorthand of a Word MediumEvery Case Spelling MediumPalindrome After a Few Fixes Medium
loading Python…
Input
first_ip='10.0.0.6', count=6
Expected
['10.0.0.6/31', '10.0.0.8/30']

Run checks the first 3 tests in your browser. Submit checks all 135 tests on the server, hidden ones included.