|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.List; |
| 4 | + |
| 5 | +/** |
| 6 | + * 751. IP to CIDR |
| 7 | + * |
| 8 | + * Given a start IP address ip and a number of ips we need to cover n, |
| 9 | + * return a representation of the range as a list (of smallest possible length) of CIDR blocks. |
| 10 | + * A CIDR block is a string consisting of an IP, followed by a slash, and then the prefix length. |
| 11 | + * For example: "123.45.67.89/20". That prefix length "20" represents the number of common prefix bits in the specified range. |
| 12 | + * |
| 13 | + * Example 1: |
| 14 | + * Input: ip = "255.0.0.7", n = 10 |
| 15 | + * Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"] |
| 16 | + * Explanation: |
| 17 | + * The initial ip address, when converted to binary, looks like this (spaces added for clarity): |
| 18 | + * 255.0.0.7 -> 11111111 00000000 00000000 00000111 |
| 19 | + * |
| 20 | + * The address "255.0.0.7/32" specifies all addresses with a common prefix of 32 bits to the given address, |
| 21 | + * ie. just this one address. |
| 22 | + * |
| 23 | + * The address "255.0.0.8/29" specifies all addresses with a common prefix of 29 bits to the given address: |
| 24 | + * 255.0.0.8 -> 11111111 00000000 00000000 00001000 |
| 25 | + * Addresses with common prefix of 29 bits are: |
| 26 | + * 11111111 00000000 00000000 00001000 |
| 27 | + * 11111111 00000000 00000000 00001001 |
| 28 | + * 11111111 00000000 00000000 00001010 |
| 29 | + * 11111111 00000000 00000000 00001011 |
| 30 | + * 11111111 00000000 00000000 00001100 |
| 31 | + * 11111111 00000000 00000000 00001101 |
| 32 | + * 11111111 00000000 00000000 00001110 |
| 33 | + * 11111111 00000000 00000000 00001111 |
| 34 | + * |
| 35 | + * The address "255.0.0.16/32" specifies all addresses with a common prefix of 32 bits to the given address, |
| 36 | + * ie. just 11111111 00000000 00000000 00010000. |
| 37 | + * |
| 38 | + * In total, the answer specifies the range of 10 ips starting with the address 255.0.0.7 . |
| 39 | + * |
| 40 | + * There were other representations, such as: |
| 41 | + * ["255.0.0.7/32","255.0.0.8/30", "255.0.0.12/30", "255.0.0.16/32"], |
| 42 | + * but our answer was the shortest possible. |
| 43 | + * |
| 44 | + * Also note that a representation beginning with say, "255.0.0.7/30" would be incorrect, |
| 45 | + * because it includes addresses like 255.0.0.4 = 11111111 00000000 00000000 00000100 |
| 46 | + * that are outside the specified range. |
| 47 | + * Note: |
| 48 | + * ip will be a valid IPv4 address. |
| 49 | + * Every implied address ip + x (for x < n) will be a valid IPv4 address. |
| 50 | + * n will be an integer in the range [1, 1000]. |
| 51 | + * */ |
| 52 | +publicclass_751 { |
| 53 | +publicstaticclassSolution1 { |
| 54 | +publicList<String>ipToCIDR(Stringip,intn) { |
| 55 | +//TODO: implement it |
| 56 | +returnnull; |
| 57 | + } |
| 58 | + } |
| 59 | +} |