# Java Solution (18ms)

• Maximize the number of trailing zeros, which will give us the largest block of IP addresses possible and optimal answer.

We can increase the number of trailing zeros by creating a CIDR block that uses all the current trailing zeros available. E.g.

...0010 = Block of 2 IP addresses available
So we create a block of 2 IP addresses and add that range to the IP = ...0010 + 0010 =
...0100 = Now a block of 4 IP addresses is available. And so forth.

In the case of the example from the problem:

...0111 = Only 1 IP address available to start. 0 trailing zeros = Block of 1 address available.
...1000 = 3 trailing zeros = Block of 8 IP addresses available. etc.

class Solution {
public List<String> ipToCIDR(String ipString, int range) {
int ip = convertStringIPtoNum(ipString);
List<String> cidrBlocks = new ArrayList<>();
while(range > 0) {
int zeros = getZeros(ip);
int thisRange = 1 << zeros;
thisRange = Math.min(range,thisRange);
getCidrBlocks(ip, thisRange, cidrBlocks);
ip += thisRange;
range -= thisRange;
}
return cidrBlocks;
}

private int getZeros(int ip) {
int zeros = 0;
for(int i = 0; i<32; i++) {
if((ip & (1 << i)) == 0) {
zeros++;
} else break;
}
return zeros;
}

private void getCidrBlocks(int ip, int range, List<String> cidrBlocks) {
if(range <= 0) return;
int i = 0;
while((1 << i+1) <= range) i++; // Get power of 2 within range
int prefixLength = 32-i;
int thisRange = 1 << i;
String ipString = convertNumToIPString(ip) + "/" + prefixLength;
getCidrBlocks(ip+thisRange,range-thisRange,cidrBlocks);
}

private String convertNumToIPString(int num) {
StringBuilder sb = new StringBuilder();

for(int i=0; i<4; i++) {
if(i>0) sb.insert(0, '.');
sb.insert(0,(num & 255));
num >>= 8;
}
return sb.toString();
}

private int convertStringIPtoNum(String ipstring) {
String[] ipArray = ipstring.split("[.]");
int ip = 0;
for(int i=0; i<4; i++) {
ip += Integer.parseInt(ipArray[i]) * (1 << (8*(3-i)));
}
return ip;
}
}

• im not sure if this is cheating but i used a method provided by jdk Integer.numberOfTrailingZeros()......

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<String> ipToCIDR(String ip, int range) {
ArrayList<String> result = new ArrayList<>();
int origin = str2Int(ip), lastCount = Integer.numberOfTrailingZeros(origin);
while (range != 0) {
int segment = (int) Math.pow(2.0, (double) lastCount);
if (segment <= range) {
result.add(int2Str(origin) + "/" + String.valueOf(32 - lastCount));
origin += segment;
range -= segment;
lastCount = Integer.numberOfTrailingZeros(origin);
} else {
lastCount--;
}
}
return result;
}

private String int2Str(int ip) {
return ((ip >> 24) & 0xFF) + "." + ((ip >> 16) & 0xFF) + "." + ((ip >> 8) & 0xFF) + "." + (ip & 0xFF);
}

private int str2Int(String ip) {
int result = 0;
String[] inArray = ip.split("\\.");
for (int i = 3; i >= 0; i--) {
result |= Integer.parseInt(inArray[3 - i]) << (i * 8);
}
return result;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.