Aggregate Two Adjacent Subnets
Problem Statement
Route summarization merges two adjacent equal-size subnets into a single shorter-prefix block when possible. Given two CIDRs of the same prefix length, return their aggregate CIDR or None if they cannot be merged.
Background
Two /p blocks aggregate into a /(p-1) block only if they are the two halves of that parent: same prefix length, and the parent's base (the /(p-1) network of the lower block) exactly contains both, with the two blocks being consecutive and non-overlapping. Concretely, they merge iff base1 % (2*size) == 0 (lower block aligned to the parent) and base2 == base1 + size, where size = 2(32-p)**.
Your Task
def aggregate(cidr_a, cidr_b):
Return the aggregated "network/prefix" string, or None.
Input Format
- cidr_a, cidr_b (str), same prefix length.
Output Format
- A CIDR string or None.
Sample
print(aggregate("10.0.0.0/24", "10.0.1.0/24"))
Output:
10.0.0.0/23
Example:
print(aggregate("10.0.0.0/24", "10.0.1.0/24"))10.0.0.0/23
-
Parse and Convert: Convert the IP addresses to 32-bit integers to facilitate arithmetic.
- 10.0.0.0→10⋅224=167,772,160
- 10.0.1.0→10⋅224+1⋅216=167,774,208
- Both have prefix length p=24.
-
Determine Block Size: Calculate the number of addresses in a single /24 subnet.
- size=232−24=28=256
-
Identify Lower and Upper Blocks: Sort the integer values to determine adjacency.
- lo=167,772,160
- hi=167,774,208
-
Check Merge Conditions: Verify that the lower block is aligned to the parent boundary and the blocks are consecutive.
- Alignment: lo(mod2⋅size)=167,772,160(mod512)=0 (Aligned)
- Adjacency: hi=lo+size→167,774,208=167,772,160+256 (True)
-
Construct Result: Since conditions are met, the aggregate network is the lower block with the prefix length decremented by 1.
- Network: 10.0.0.0
- New Prefix: 24−1=23
- The final output is
10.0.0.0/23
Constraints:
- Both must share the prefix length
p. - Merge only if the lower base is aligned to
2*sizeand the upper base is exactlysizehigher. - Return the
/(p-1)CIDR, else None.
1. Background Knowledge
CIDR (Classless Inter-Domain Routing) notation expresses an IP network as address/prefix. The prefix length p indicates how many leading bits are fixed; the remaining 32−p bits identify individual hosts within that block. A /24 block, for example, contains 232−24=256 addresses.
Route summarization (or supernetting) collapses two adjacent, equal-size subnets into one larger block when they form the two halves of a parent network. Two /p blocks can merge into a /(p-1) block only if they are consecutive and the lower block is aligned to the parent boundary. Alignment means the lower block's base address is a multiple of the parent's size, i.e., base_lower % (2 * size) == 0, where size = 2(32 - p)**.
To work with IP addresses arithmetically, convert each dotted-quad string to a 32-bit integer. Python's ipaddress module provides ip_address() and ip_network() helpers that handle this conversion and prefix validation, making the arithmetic straightforward.
2. Algorithm Approach
The problem reduces to a boundary and alignment check on two integer representations of network base addresses:
- Parse both CIDR strings into their integer base addresses and prefix length.
- Verify both share the same prefix length.
- Identify the lower and upper base addresses.
- Check two conditions:
- Adjacency: upper == lower + size, where size = 2(32 - p)**.
- Alignment: lower % (2 * size) == 0.
- If both hold, the aggregate is the lower base with prefix p - 1. Otherwise, return None.
This is a constant-time arithmetic check—no iteration or tree traversal is needed.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.