IP to CIDR

Problem

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.

For example, the binary number 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 firstk bits are the same as the base IP address.

For example, "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 theshortest list of CIDR blocks that covers the range of IP addresses. If there are multiple answers, return any of them.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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:

1
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 <= 15
ip 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 <= 1000
Every implied address ip + x (for x < n) will be a valid IPv4 address.

Solution

Method 1 – Bit Manipulation and Greedy

Intuition

To cover a range of IPs with the fewest CIDR blocks, always use the largest block possible at each step. This is determined by the lowest set bit in the current IP and the number of IPs left to cover.

Approach

Convert the start IP to an integer.
While there are IPs left to cover:
- Find the largest block size that fits the current IP (using the lowest set bit).
- Limit the block size so it does not exceed the number of IPs left.
- Add the corresponding CIDR block to the answer.
- Move to the next IP and decrease the count.
Convert integer IPs back to string format for the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    vector<string> ipToCIDR(string ip, int n) {
        vector<string> ans;
        long x = 0;
        for (auto c : ip) if (c != '.') x = x * 256 + (c - '0');
        while (n > 0) {
            long lb = x & -x;
            int maxSize = 1;
            while (maxSize <= n && maxSize <= lb) maxSize <<= 1;
            maxSize >>= 1;
            int len = 32 - __builtin_ctz(maxSize);
            ans.push_back(toIP(x) + "/" + to_string(len));
            x += maxSize;
            n -= maxSize;
        }
        return ans;
    }
    string toIP(long x) {
        return to_string((x>>24)&255) + "." + to_string((x>>16)&255) + "." + to_string((x>>8)&255) + "." + to_string(x&255);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func ipToCIDR(ip string, n int) []string {
    var ans []string
    x := 0
    for _, c := range strings.Split(ip, ".") {
        v, _ := strconv.Atoi(c)
        x = x*256 + v
    }
    for n > 0 {
        lb := x & -x
        maxSize := 1
        for maxSize <= n && maxSize <= lb {
            maxSize <<= 1
        }
        maxSize >>= 1
        len := 32 - bits.TrailingZeros(uint(maxSize))
        ans = append(ans, toIP(x)+"/"+strconv.Itoa(len))
        x += maxSize
        n -= maxSize
    }
    return ans
}
func toIP(x int) string {
    return fmt.Sprintf("%d.%d.%d.%d", (x>>24)&255, (x>>16)&255, (x>>8)&255, x&255)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        List<String> ans = new ArrayList<>();
        long x = 0;
        for (String s : ip.split("\\.")) x = x * 256 + Integer.parseInt(s);
        while (n > 0) {
            long lb = x & -x;
            int maxSize = 1;
            while (maxSize <= n && maxSize <= lb) maxSize <<= 1;
            maxSize >>= 1;
            int len = 32 - Long.numberOfTrailingZeros(maxSize);
            ans.add(toIP(x) + "/" + len);
            x += maxSize;
            n -= maxSize;
        }
        return ans;
    }
    String toIP(long x) {
        return String.format("%d.%d.%d.%d", (x>>24)&255, (x>>16)&255, (x>>8)&255, x&255);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    fun ipToCIDR(ip: String, n: Int): List<String> {
        var x = ip.split('.').fold(0L) { acc, s -> acc * 256 + s.toLong() }
        var cnt = n
        val ans = mutableListOf<String>()
        while (cnt > 0) {
            val lb = x and -x
            var maxSize = 1L
            while (maxSize <= cnt && maxSize <= lb) maxSize = maxSize shl 1
            maxSize = maxSize shr 1
            val len = 32 - maxSize.countTrailingZeroBits()
            ans.add(toIP(x) + "/$len")
            x += maxSize
            cnt -= maxSize.toInt()
        }
        return ans
    }
    fun toIP(x: Long) = listOf((x shr 24) and 255, (x shr 16) and 255, (x shr 8) and 255, x and 255).joinToString(".")
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


def ip_to_cidr(ip: str, n: int) -> list[str]:
    def ip2int(ip):
        ans = 0
        for x in ip.split('.'):
            ans = ans * 256 + int(x)
        return ans
    def int2ip(x):
        return '.'.join(str((x >> (8*i)) & 255) for i in (3,2,1,0))
    x = ip2int(ip)
    ans = []
    while n > 0:
        lb = x & -x
        max_size = 1
        while max_size <= n and max_size <= lb:
            max_size <<= 1
        max_size >>= 1
        length = 32 - (max_size.bit_length() - 1)
        ans.append(f"{int2ip(x)}/{length}")
        x += max_size
        n -= max_size
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


fn ip_to_cidr(ip: &str, mut n: i32) -> Vec<String> {
    let mut x = ip.split('.').fold(0u32, |acc, s| acc * 256 + s.parse::<u32>().unwrap());
    let mut ans = vec![];
    while n > 0 {
        let lb = x & x.wrapping_neg();
        let mut max_size = 1u32;
        while max_size <= n as u32 && max_size <= lb {
            max_size <<= 1;
        }
        max_size >>= 1;
        let len = 32 - max_size.trailing_zeros();
        ans.push(format!("{}.{}.{}.{}/{}", (x>>24)&255, (x>>16)&255, (x>>8)&255, x&255, len));
        x += max_size;
        n -= max_size as i32;
    }
    ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
  ipToCIDR(ip: string, n: number): string[] {
    function ip2int(ip: string): number {
      return ip.split('.').reduce((acc, x) => acc * 256 + +x, 0);
    }
    function int2ip(x: number): string {
      return [24,16,8,0].map(s => (x >> s) & 255).join('.');
    }
    let x = ip2int(ip);
    const ans: string[] = [];
    while (n > 0) {
      let lb = x & -x;
      let maxSize = 1;
      while (maxSize <= n && maxSize <= lb) maxSize <<= 1;
      maxSize >>= 1;
      const len = 32 - Math.clz32(maxSize);
      ans.push(`${int2ip(x)}/${len}`);
      x += maxSize;
      n -= maxSize;
    }
    return ans;
  }
}

Complexity

⏰ Time complexity: O(log n) — Each step covers at least one IP, and the number of steps is proportional to the number of bits in n.
🧺 Space complexity: O(1) — Only a few variables and the result list are used.

Problem#

Examples#

Solution#

Method 1 – Bit Manipulation and Greedy#

Intuition#

Approach#

Code#

Complexity#