IP to CIDR - Practice Coding Problems

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 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 consists 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.

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 covered by this CIDR block.

Given a start IP address ip and the number of IP addresses we need to cover n, return the shortest list of CIDR blocks that covers all IP addresses in the inclusive range [ip, ip + n - 1] exactly. No other IP addresses outside of the range should be covered.

Input & Output

Example 1 — Basic Range

$ Input: ip = "255.255.255.7", n = 10

› Output: ["255.255.255.7/32","255.255.255.8/29","255.255.255.16/32"]

💡 Note: Start at 255.255.255.7 (binary ends in ...111, no trailing zeros), so single IP block /32. Then 255.255.255.8 (ends in ...1000, 3 trailing zeros) can use /29 block covering 8 IPs. Finally, one more /32 for the remaining IP.

Example 2 — Small Range

$ Input: ip = "1.1.1.1", n = 1

› Output: ["1.1.1.1/32"]

💡 Note: Single IP address gets a /32 CIDR block covering exactly that one IP.

Example 3 — Aligned Range

$ Input: ip = "192.168.1.0", n = 4

› Output: ["192.168.1.0/30"]

💡 Note: Starting IP ends in ...00 (2 trailing zeros), and we need exactly 4 IPs (2²), so one /30 block perfectly covers the range 192.168.1.0 to 192.168.1.3.

Constraints

ip is a valid IPv4 address
1 ≤ n ≤ 1000
The range [ip, ip + n - 1] will not overflow

Visualization

Tap to expand

Understanding the Visualization

Input

Start IP and count of consecutive IPs needed

Process

Use bit manipulation to find optimal CIDR block sizes

Output

Minimal list of CIDR blocks covering the range

Key Takeaway

🎯 Key Insight: Use trailing zeros in IP binary representation to determine maximum possible block size, then apply greedy selection for optimal coverage.

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use bit manipulation to find the largest possible CIDR blocks. The maximum block size at any position is limited by the number of trailing zeros in the IP address and the remaining count. The greedy approach always selects the largest valid block, minimizing the total number of blocks needed. Time: O(log n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Bit Manipulation	O(log n)	O(log n)	Always choose the largest possible CIDR block that fits
Individual IP Blocks	O(n)	O(n)	Create one /32 CIDR block for each IP address

Greedy Bit Manipulation — Algorithm Steps

Convert IP to integer
While count > 0: find max block size using trailing zeros and remaining count
Create CIDR block and update position
Continue until all IPs covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Start IP

Find trailing zeros to determine max block size

Choose Block

Select largest block that fits within remaining count

Repeat

Continue until all IPs are covered

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

unsigned int ipToInt(const char* ip) {
    unsigned int a, b, c, d;
    sscanf(ip, "%u.%u.%u.%u", &a, &b, &c, &d);
    return (a << 24) + (b << 16) + (c << 8) + d;
}

void intToIp(unsigned int ip, char* result) {
    sprintf(result, "%u.%u.%u.%u", 
        (ip >> 24) & 255, (ip >> 16) & 255, 
        (ip >> 8) & 255, ip & 255);
}

char** solution(char* ip, int n, int* returnSize) {
    unsigned int start = ipToInt(ip);
    char** result = malloc(32 * sizeof(char*));
    int count = 0;
    
    while (n > 0) {
        // Find trailing zeros
        int trailingZeros = 0;
        unsigned int temp = start;
        while ((temp & 1) == 0 && temp != 0) {
            trailingZeros++;
            temp >>= 1;
        }
        
        unsigned int maxBlockSize = 1U << trailingZeros;
        
        // Limit by remaining count
        while (maxBlockSize > n) {
            maxBlockSize >>= 1;
        }
        
        // Find largest power of 2 <= n and <= maxBlockSize
        unsigned int blockSize = 1;
        while (blockSize <= n && blockSize <= maxBlockSize) {
            blockSize <<= 1;
        }
        blockSize >>= 1;
        
        // Create CIDR block
        int prefixLen = 32 - (int)log2(blockSize);
        char ipStr[16];
        intToIp(start, ipStr);
        result[count] = malloc(25 * sizeof(char));
        sprintf(result[count], "%s/%d", ipStr, prefixLen);
        count++;
        
        start += blockSize;
        n -= blockSize;
    }
    
    *returnSize = count;
    return result;
}

int main() {
    char ip[16];
    int n;
    fgets(ip, sizeof(ip), stdin);
    ip[strcspn(ip, "\n")] = 0;
    scanf("%d", &n);
    
    int returnSize;
    char** result = solution(ip, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each iteration reduces remaining count by at least half in worst case

⚡ Linearithmic

Space Complexity

O(log n)

Result list contains at most log(n) CIDR blocks

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler