Description
Seven different symbols represent Roman numerals with the following values:
| Symbol |
Value |
| I |
1 |
| V |
5 |
| X |
10 |
| L |
50 |
| C |
100 |
| D |
500 |
| M |
1000 |
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
- If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
- If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (
I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
- Only powers of 10 (
I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Given an integer, convert it to a Roman numeral.
Example 1:
Input: num = 3749
Output: "MMMDCCXLIX"
Explanation:
3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
Example 2:
Input: num = 58
Output: "LVIII"
Explanation:
50 = L
8 = VIII
Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation:
1000 = M
900 = CM
90 = XC
4 = IV
Constraints:
Solutions
Solution 1: Greedy
We can first list all possible symbols cs and their corresponding values vs, then enumerate each value vs[i] from large to small. Each time, we use as many symbols cs[i] corresponding to this value as possible, until the number num becomes 0.
The time complexity is O(m), and the space complexity is O(m). Here, m is the number of symbols.
PythonJavaC++GoTypeScriptRustC#PHPC
class Solution:
def intToRoman(self, num: int) -> str:
cs = ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')
vs = (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
ans = []
for c, v in zip(cs, vs):
while num >= v:
num -= v
ans.append(c)
return ''.join(ans)(code-box)
class Solution {
public String intToRoman(int num) {
List<String> cs
= List.of("M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I");
List<Integer> vs = List.of(1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1);
StringBuilder ans = new StringBuilder();
for (int i = 0, n = cs.size(); i < n; ++i) {
while (num >= vs.get(i)) {
num -= vs.get(i);
ans.append(cs.get(i));
}
}
return ans.toString();
}
}(code-box)
class Solution {
public:
string intToRoman(int num) {
vector<string> cs = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
vector<int> vs = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string ans;
for (int i = 0; i < cs.size(); ++i) {
while (num >= vs[i]) {
num -= vs[i];
ans += cs[i];
}
}
return ans;
}
};(code-box)
func intToRoman(num int) string {
cs := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
vs := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
ans := &strings.Builder{}
for i, v := range vs {
for num >= v {
num -= v
ans.WriteString(cs[i])
}
}
return ans.String()
}(code-box)
function intToRoman(num: number): string {
const cs: string[] = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
const vs: number[] = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
const ans: string[] = [];
for (let i = 0; i < vs.length; ++i) {
while (num >= vs[i]) {
num -= vs[i];
ans.push(cs[i]);
}
}
return ans.join('');
}(code-box)
impl Solution {
pub fn int_to_roman(num: i32) -> String {
let cs = [
"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I",
];
let vs = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
let mut num = num;
let mut ans = String::new();
for (i, &v) in vs.iter().enumerate() {
while num >= v {
num -= v;
ans.push_str(cs[i]);
}
}
ans
}
}(code-box)
public class Solution {
public string IntToRoman(int num) {
List<string> cs = new List<string>{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
List<int> vs = new List<int>{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
StringBuilder ans = new StringBuilder();
for (int i = 0; i < cs.Count; i++) {
while (num >= vs[i]) {
ans.Append(cs[i]);
num -= vs[i];
}
}
return ans.ToString();
}
}(code-box)
class Solution {
/**
* @param Integer $num
* @return String
*/
function intToRoman($num) {
$cs = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
$vs = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
$ans = '';
foreach ($vs as $i => $v) {
while ($num >= $v) {
$num -= $v;
$ans .= $cs[$i];
}
}
return $ans;
}
}(code-box)
static const char* cs[] = {
"M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I"};
static const int vs[] = {
1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 1};
char* intToRoman(int num) {
static char ans[20];
ans[0] = '\0';
for (int i = 0; i < 13; ++i) {
while (num >= vs[i]) {
num -= vs[i];
strcat(ans, cs[i]);
}
}
return ans;
}(code-box)
