# 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> 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 M{"", "M", "MM", "MMM"}; const vector C{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; const vector X{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; const vector 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]