Skip to content

751. IP to CIDR 👎

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
 public:
  vector<string> ipToCIDR(string ip, int n) {
    vector<string> ans;
    long num = getNum(ip);

    while (n > 0) {
      const long lowbit = num & -num;
      const long count = lowbit == 0 ? maxLow(n) : firstFit(lowbit, n);
      ans.push_back(getCIDR(num, getPrefix(count)));
      n -= count;
      num += count;
    }

    return ans;
  }

 private:
  long getNum(const string& ip) {
    istringstream iss(ip);
    long num = 0;
    for (string token; getline(iss, token, '.');)
      num = num * 256 + stol(token);
    return num;
  }

  // Returns the maximum i s.t. 2^i < n.
  int maxLow(int n) {
    for (int i = 0; i < 32; ++i)
      if (1 << i + 1 > n)
        return 1 << i;
    throw;
  }

  long firstFit(long lowbit, long n) {
    while (lowbit > n)
      lowbit >>= 1;
    return lowbit;
  }

  string getCIDR(long num, long prefix) {
    const long d = num & 255;
    num >>= 8;
    const long c = num & 255;
    num >>= 8;
    const long b = num & 255;
    num >>= 8;
    const long a = num & 255;
    return to_string(a) + '.' + to_string(b) + '.' + to_string(c) + '.' +
           to_string(d) + '/' + to_string(prefix);
  }

  // e.g. count = 8 = 2^3 -> prefix = 32 - 3 = 29
  //      count = 1 = 2^0 -> prefix = 32 - 0 = 32
  int getPrefix(long count) {
    for (int i = 0; i < 32; ++i)
      if (count == 1 << i)
        return 32 - i;
    throw;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
  public List<String> ipToCIDR(String ip, int n) {
    List<String> ans = new ArrayList<>();
    long num = getNum(ip.split("\\."));

    while (n > 0) {
      final long lowbit = num & -num;
      final long count = lowbit == 0 ? maxLow(n) : firstFit(lowbit, n);
      ans.add(getCIDR(num, getPrefix(count)));
      n -= (int) count;
      num += count;
    }

    return ans;
  }

  private long getNum(String[] x) {
    long num = 0;
    for (int i = 0; i < 4; ++i)
      num = num * 256 + Long.parseLong(x[i]);
    return num;
  }

  // Returns the maximum i s.t. 2^i < n.
  private int maxLow(int n) {
    for (int i = 0; i < 32; ++i)
      if (1 << i + 1 > n)
        return 1 << i;
    throw new IllegalArgumentException();
  }

  private long firstFit(long lowbit, long n) {
    while (lowbit > n)
      lowbit >>= 1;
    return lowbit;
  }

  private String getCIDR(long num, long prefix) {
    final long d = num & 255;
    num >>= 8;
    final long c = num & 255;
    num >>= 8;
    final long b = num & 255;
    num >>= 8;
    final long a = num & 255;
    return new StringBuilder()
        .append(a)
        .append(".")
        .append(b)
        .append(".")
        .append(c)
        .append(".")
        .append(d)
        .append("/")
        .append(prefix)
        .toString();
  }

  // e.g. count = 8 = 2^3 -> prefix = 32 - 3 = 29
  //      count = 1 = 2^0 -> prefix = 32 - 0 = 32
  private int getPrefix(long count) {
    for (int i = 0; i < 32; ++i)
      if (count == 1 << i)
        return 32 - i;
    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
  def ipToCIDR(self, ip: str, n: int) -> list[str]:
    ans = []
    num = self._getNum(ip.split('.'))

    while n > 0:
      lowbit = num & -num
      count = self._maxLow(n) if lowbit == 0 else self._firstFit(lowbit, n)
      ans.append(self._getCIDR(num, self._getPrefix(count)))
      n -= count
      num += count

    return ans

  def _getNum(self, x: list[str]) -> int:
    num = 0
    for i in range(4):
      num = num * 256 + int(x[i])
    return num

  def _maxLow(self, n: int) -> int | None:
    """Returns the maximum i s.t. 2^i < n."""
    for i in range(32):
      if 1 << i + 1 > n:
        return 1 << i

  def _firstFit(self, lowbit: int, n: int) -> int:
    while lowbit > n:
      lowbit >>= 1
    return lowbit

  def _getCIDR(self, num: int, prefix: int) -> str:
    d = num & 255
    num >>= 8
    c = num & 255
    num >>= 8
    b = num & 255
    num >>= 8
    a = num & 255
    return '.'.join([str(s) for s in [a, b, c, d]]) + '/' + str(prefix)

  def _getPrefix(self, count: int) -> int | None:
    """
    e.g. count = 8 = 2^3 . prefix = 32 - 3 = 29
         count = 1 = 2^0 . prefix = 32 - 0 = 32
    """
    for i in range(32):
      if count == 1 << i:
        return 32 - i