IP to CIDR

Medium Bit Manipulation Tricks to remember Original on LeetCode

Reported atAirbnbDatabricks

IP to CIDR is a medium bit manipulation problem solved with the tricks to remember pattern. The best approach, optimal (largest aligned block via lowest set bit), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one block per address, then merge buddies) up.

Problem

An IPv4 address is a 32-bit number written as four bytes in decimal separated by dots, like "10.0.0.5". A CIDR block "a.b.c.d/k" stands for every address whose first k bits match those of a.b.c.d, which is a run of 2^(32 - k) consecutive addresses. In this problem the address before the slash must be the first address of its block, so its last 32 - k bits are all zero.

Given a starting address ip and a count n, return the shortest list of CIDR blocks that together cover exactly the n consecutive addresses ip, ip + 1, ..., ip + n - 1 and nothing else. List the blocks in increasing order of address.

Examples

Example 1

Input
ip = "10.0.0.5", n = 6
Output
["10.0.0.5/32", "10.0.0.6/31", "10.0.0.8/31", "10.0.0.10/32"]
Why
The addresses end in 5 to 10. Address 5 is odd so it stands alone; 6-7 and 8-9 are aligned pairs; 10 is left over.

Example 2

Input
ip = "192.168.1.0", n = 256
Output
["192.168.1.0/24"]
Why
The range starts on a multiple of 256 and is exactly 256 long, so one /24 block covers it.

Example 3

Input
ip = "172.16.0.255", n = 3
Output
["172.16.0.255/32", "172.16.1.0/31"]
Why
The range crosses into the next third octet: .0.255 alone, then the aligned pair 1.0-1.1.

Constraints

  • ip is a valid IPv4 address in dotted form (four numbers from 0 to 255, no leading zeros).
  • 1 <= n <= 1000
  • The last address of the range, ip + n - 1, is at most 255.255.255.255.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (one block per address, then merge buddies)O(n)O(n)
Optimal (largest aligned block via lowest set bit)O(log n)O(1)

1Brute force (one block per address, then merge buddies)

TimeO(n)Every address is pushed once, and each merge removes a block, so there are fewer than n merges.
SpaceO(n)The stack can hold up to n blocks during the merging (and log n afterwards).

Begin with a separate /32 block for every address in the range and merge on a stack. Two neighboring blocks of the same size can be merged when the lower one starts at a multiple of twice that size, because together they form one aligned block. Merging until nothing more combines leaves the fewest blocks.

  1. Convert ip to a number start.
  2. For each address x from start to start + n - 1, push the block (x, 1).
  3. After each push, while the top two blocks have the same size s, are adjacent, and the lower starts at a multiple of 2s, replace them with (lower, 2s).
  4. Format each remaining block as its dotted start plus / and 32 - log2(size).
class Solution {
    private String format(long x, long size) {
        int bits = 0;
        while ((1L << bits) < size) bits++;
        return ((x >> 24) & 255) + "." + ((x >> 16) & 255) + "." + ((x >> 8) & 255) + "." + (x & 255) + "/" + (32 - bits);
    }

    public List<String> ipToCIDR(String ip, int n) {
        long start = 0;
        for (String part : ip.split("\\.")) start = start * 256 + Integer.parseInt(part);
        List<long[]> stack = new ArrayList<>();
        for (long x = start; x < start + n; x++) {
            stack.add(new long[] { x, 1 });
            while (stack.size() >= 2) {
                long[] b = stack.get(stack.size() - 1), a = stack.get(stack.size() - 2);
                if (a[1] != b[1] || a[0] + a[1] != b[0] || a[0] % (2 * a[1]) != 0) break;
                stack.remove(stack.size() - 1);
                a[1] *= 2;
            }
        }
        List<String> res = new ArrayList<>();
        for (long[] block : stack) res.add(format(block[0], block[1]));
        return res;
    }
}

2Optimal (largest aligned block via lowest set bit)

TimeO(log n)Block sizes rise and then fall as powers of two, so there are O(log n) blocks, each needing O(32) bit work.
SpaceO(1)Only a few numbers are kept, apart from the output list.

Jump block by block instead of address by address. At the current start x, the largest block that is aligned at x has size equal to the lowest set bit of x (any size for x = 0). Halve it while it is larger than the number of addresses still needed, emit it, and move x forward by that size.

  1. Convert ip to a 64-bit number x.
  2. While n > 0: let size = x & -x (or 2^32 when x is 0).
  3. While size > n, halve size.
  4. Emit dotted(x) + "/" + (32 - log2(size)), then x += size and n -= size.
class Solution {
    public List<String> ipToCIDR(String ip, int n) {
        long x = 0;
        for (String part : ip.split("\\.")) x = x * 256 + Integer.parseInt(part);
        List<String> res = new ArrayList<>();
        while (n > 0) {
            long size = x == 0 ? 1L << 32 : x & -x;
            while (size > n) size >>= 1;
            int bits = Long.numberOfTrailingZeros(size);
            res.add(((x >> 24) & 255) + "." + ((x >> 16) & 255) + "." + ((x >> 8) & 255) + "." + (x & 255) + "/" + (32 - bits));
            x += size;
            n -= (int) size;
        }
        return res;
    }
}

Edge cases to test

  • n = 1, which always gives a single /32
  • Starting at 0.0.0.0, where every block size is aligned
  • Ranges that cross an octet boundary, like x.y.z.255
  • An odd starting address, which forces a /32 first

Hints

Hint 1

Turn the address into one 32-bit number. A block a/k covers 2^(32-k) addresses and is only valid when the start is a multiple of that size.

Hint 2

Being greedy works: at the current start, use the largest block that is aligned at that start and does not cover more addresses than are still needed.

Hint 3

The largest aligned size at x is the lowest set bit of x (x & -x), halved until it is no larger than the remaining count.

FAQ

What is the best time complexity for IP to CIDR?

Optimal (largest aligned block via lowest set bit) runs in O(log n) time and O(1) extra space. Block sizes rise and then fall as powers of two, so there are O(log n) blocks, each needing O(32) bit work.

Which pattern does IP to CIDR use?

It is a bit manipulation problem that uses the tricks to remember pattern. Other problems with the same pattern: Number of 1 Bits, Set the rightmost unset bit, XOR of 1 to n Numbers.

Is there a brute force solution for IP to CIDR?

Yes. Brute force (one block per address, then merge buddies) takes O(n) time and O(n) space. Begin with a separate /32 block for every address in the range and merge on a stack.

Which edge cases should I test for IP to CIDR?

n = 1, which always gives a single /32; Starting at 0.0.0.0, where every block size is aligned; Ranges that cross an octet boundary, like x.y.z.255; An odd starting address, which forces a /32 first.