Java Solution (13 ms) - no extra memory


  • 0
    M
    class Solution {
      public List<String> ipToCIDR(String ip, int n) {
        long num = ipToLong(ip);
        List<String> res = new LinkedList<>();
        long max = n + num - 1;
        for(long ipNum = num; ipNum < n + num; ipNum++){
          int idx = getLeastOne(ipNum);
          while(idx > 0 && (ipNum | (1 << idx) - 1) > max){
            idx --;
          }
          res.add(longToCIDR(ipNum, idx));
          ipNum += (1 << idx) - 1;
        }
        return res;
      }
    
      private long ipToLong(String ip){
        String [] strs = ip.split("\\.");
        long num = 0;
        for(int i = 0; i < strs.length; i++){
          num <<= 8;
          num |= Long.parseLong(strs[i]);
        }
        return num;
      }
    
      private int getLeastOne(long ipNum){
        int idx = 0;
        while((ipNum & 1) == 0){
          idx ++;
          ipNum >>= 1;
        }
        return idx;
      }
    
      private String longToCIDR(long ipNum, int idx){
        long [] ipArray = new long[4];
        for(int i = 0; i < ipArray.length; i++){
          ipArray[i] = ipNum & ((1<<8) - 1);
          ipNum >>= 8;
        }
        StringBuilder builder = new StringBuilder();
        for(int i = 3; i >= 0; i--){
          builder.append(ipArray[i]);
          if(i > 0){
            builder.append(".");
          }
        }
        builder.append("/").append(32-idx);
        return builder.toString();
      }
    }
    
    

Log in to reply
 

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