12. Integer to Roman

Posted on Edited on In

12. Integer to Roman

Description

Seven different symbols represent Roman numerals with the following values:

SymbolValue
I1
V5
X10
L50
C100
D500
M1000

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 or9, 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): IVand 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:

1
2
3
4
5
6
7
8
9
10
11
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:

1
2
3
4
5
6
7
8
Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

1
2
3
4
5
6
7
8
9
10
Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

Constraints:

  • 1 <= num <= 3999

Hints/Notes

Solution

Language: C++

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
class Solution {
public:
    string intToRoman(int num) {
        char ONE = 'I', FIVE = 'V', TEN = 'X', FIFTY = 'L', HUNDRED = 'C', FIVEHUNDRED = 'D', THOUSAND = 'M';
        string res;
        if (num >= 1000) {
            int thousand = num / 1000;
            string t(thousand, 'M');
            res += t;
            num %= 1000;
        }
        if (num >= 100) {
            int hundred = num / 100;
            string h;
            if (hundred == 4) {
                h = "CD";
            } else if (hundred == 9) {
                h = "CM";
            } else {
                if (hundred >= 5) {
                    h.push_back('D');
                    hundred -= 5;
                }
                h += string(hundred, 'C');
            }
            res += h;
            num %= 100;
        }
        if (num >= 10) {
            int tens = num / 10;
            string ten;
            if (tens == 4) {
                ten = "XL";
            } else if (tens == 9) {
                ten = "XC";
            } else {
                if (tens >= 5) {
                    ten.push_back('L');
                    tens -= 5;
                }
                ten += string(tens, 'X');
            }
            res += ten;
            num %= 10;
        }
        if (num > 0) {
            string digit;
            if (num == 4) {
                digit = "IV";
            } else if (num == 9) {
                digit = "IX";
            } else {
                if (num >= 5) {
                    digit.push_back('V');
                    num -= 5;
                }
                digit += string(num, 'I');
            }
            res += digit;
        }
        return res;
    }
};