Watch 5 video solutions for IP to CIDR, a medium level problem involving String, Bit Manipulation. This walkthrough by Shuo Yan has 2,547 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An IP address is a formatted 32-bit unsigned integer where each group of 8 bits is printed as a decimal number and the dot character '.' splits the groups.
00001111 10001000 11111111 01101011 (spaces added for clarity) formatted as an IP address would be "15.136.255.107".A CIDR block is a format used to denote a specific set of IP addresses. It is a string consisting of a base IP address, followed by a slash, followed by a prefix length k. The addresses it covers are all the IPs whose first k bits are the same as the base IP address.
"123.45.67.89/20" is a CIDR block with a prefix length of 20. Any IP address whose binary representation matches 01111011 00101101 0100xxxx xxxxxxxx, where x can be either 0 or 1, is in the set covered by the CIDR block.You are given a start IP address ip and the number of IP addresses we need to cover n. Your goal is to use as few CIDR blocks as possible to cover all the IP addresses in the inclusive range [ip, ip + n - 1] exactly. No other IP addresses outside of the range should be covered.
Return the shortest list of CIDR blocks that covers the range of IP addresses. If there are multiple answers, return any of them.
Example 1:
Input: ip = "255.0.0.7", n = 10 Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"] Explanation: The IP addresses that need to be covered are: - 255.0.0.7 -> 11111111 00000000 00000000 00000111 - 255.0.0.8 -> 11111111 00000000 00000000 00001000 - 255.0.0.9 -> 11111111 00000000 00000000 00001001 - 255.0.0.10 -> 11111111 00000000 00000000 00001010 - 255.0.0.11 -> 11111111 00000000 00000000 00001011 - 255.0.0.12 -> 11111111 00000000 00000000 00001100 - 255.0.0.13 -> 11111111 00000000 00000000 00001101 - 255.0.0.14 -> 11111111 00000000 00000000 00001110 - 255.0.0.15 -> 11111111 00000000 00000000 00001111 - 255.0.0.16 -> 11111111 00000000 00000000 00010000 The CIDR block "255.0.0.7/32" covers the first address. The CIDR block "255.0.0.8/29" covers the middle 8 addresses (binary format of 11111111 00000000 00000000 00001xxx). The CIDR block "255.0.0.16/32" covers the last address. Note that while the CIDR block "255.0.0.0/28" does cover all the addresses, it also includes addresses outside of the range, so we cannot use it.
Example 2:
Input: ip = "117.145.102.62", n = 8 Output: ["117.145.102.62/31","117.145.102.64/30","117.145.102.68/31"]
Constraints:
7 <= ip.length <= 15ip is a valid IPv4 on the form "a.b.c.d" where a, b, c, and d are integers in the range [0, 255].1 <= n <= 1000ip + x (for x < n) will be a valid IPv4 address.Problem Overview: You receive a starting IPv4 address and an integer n representing how many consecutive IP addresses must be covered. The task is to return the smallest list of CIDR blocks that exactly cover this range without exceeding it.
Approach 1: Sequential Expansion (Brute Force) (Time: O(n), Space: O(n))
The straightforward method converts the starting IP to a 32‑bit integer and iterates through all n addresses. Each address could theoretically be emitted as a /32 CIDR block. While correct, this completely ignores CIDR aggregation and produces the maximum number of blocks. The algorithm performs simple integer increments and string formatting for every address. This approach helps verify correctness when learning how IPv4 addresses map to integers, but it is not practical when n becomes large.
Approach 2: Greedy Bit Manipulation (Optimal) (Time: O(k), Space: O(1))
The efficient solution converts the IP string into a 32‑bit integer and repeatedly selects the largest valid CIDR block starting at that address. Two constraints determine the block size: alignment of the current IP (derived from the lowest set bit using x & -x) and the remaining number of addresses n. The algorithm picks the largest power‑of‑two block that does not exceed either constraint. After emitting that CIDR block, increment the base address by the block size and decrease n. Each iteration produces one CIDR entry, so runtime depends on the number of blocks generated rather than the number of addresses.
This approach relies heavily on bit manipulation to detect alignment boundaries and compute valid prefix lengths. Converting between dotted IP strings and integers involves simple shifts and masks, which is a common pattern in string parsing problems. The greedy choice works because CIDR blocks must always align to powers of two.
Recommended for interviews: Interviewers expect the greedy bitwise solution. It demonstrates understanding of IPv4 binary representation, CIDR prefix rules, and efficient range covering. Showing the brute force idea first proves you understand the problem, but implementing the greedy block expansion with x & -x shows strong algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential Expansion (Brute Force) | O(n) | O(n) | Useful for understanding IP-to-integer conversion or verifying correctness for small ranges |
| Greedy Bit Manipulation (CIDR Aggregation) | O(k) | O(1) | Best approach for interviews and production; generates the minimal number of CIDR blocks |