Java Solution (18ms)


  • 4

    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.

    IP address bits:
    ...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.
    After we add 1 to the IP address:
    ...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;
            cidrBlocks.add(ipString);
            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;
        }
    }
    

  • 1

    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;
        }
    }
    

Log in to reply
 

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