Skip to content

12. Integer to Roman

Approach 1: Greedy

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  string intToRoman(int num) {
    const vector<pair<int, string>> valueSymbols{
        {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
        {90, "XC"},  {50, "L"},   {40, "XL"}, {10, "X"},   {9, "IX"},
        {5, "V"},    {4, "IV"},   {1, "I"}};
    string ans;

    for (const auto& [value, symbol] : valueSymbols) {
      if (num == 0)
        break;
      while (num >= value) {
        num -= value;
        ans += symbol;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public String intToRoman(int num) {
    final int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    final String[] symbols = {"M",  "CM", "D",  "CD", "C",  "XC", "L",
                              "XL", "X",  "IX", "V",  "IV", "I"};
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < values.length; ++i) {
      if (num == 0)
        break;
      while (num >= values[i]) {
        num -= values[i];
        sb.append(symbols[i]);
      }
    }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def intToRoman(self, num: int) -> str:
    valueSymbols = [(1000, 'M'), (900, 'CM'),
                    (500, 'D'), (400, 'CD'),
                    (100, 'C'), (90, 'XC'),
                    (50, 'L'), (40, 'XL'),
                    (10, 'X'), (9, 'IX'),
                    (5, 'V'), (4, 'IV'),
                    (1, 'I')]
    ans = []

    for value, symbol in valueSymbols:
      if num == 0:
        break
      count, num = divmod(num, value)
      ans.append(symbol * count)

    return ''.join(ans)

Approach 2: Hash Table

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  string intToRoman(int num) {
    const vector<string> M{"", "M", "MM", "MMM"};
    const vector<string> C{"",  "C",  "CC",  "CCC",  "CD",
                           "D", "DC", "DCC", "DCCC", "CM"};
    const vector<string> X{"",  "X",  "XX",  "XXX",  "XL",
                           "L", "LX", "LXX", "LXXX", "XC"};
    const vector<string> I{"",  "I",  "II",  "III",  "IV",
                           "V", "VI", "VII", "VIII", "IX"};
    return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] +
           I[num % 10];
  }
};

1
2
3
4
5
6
7
8
9
class Solution {
  public String intToRoman(int num) {
    final String[] M = {"", "M", "MM", "MMM"};
    final String[] C = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    final String[] X = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    final String[] I = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] + I[num % 10];
  }
}

1
2
3
4
5
6
7
class Solution:
  def intToRoman(self, num: int) -> str:
    M = ['', 'M', 'MM', 'MMM']
    C = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
    X = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
    I = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
    return M[num // 1000] + C[num % 1000 // 100] + X[num % 100 // 10] + I[num % 10]