-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path12.integer-to-roman.cpp
More file actions
114 lines (108 loc) · 2.55 KB
/
12.integer-to-roman.cpp
File metadata and controls
114 lines (108 loc) · 2.55 KB
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
// Tag: Hash Table, Math, String
// Time: O(N)
// Space: O(1)
// Ref: -
// Note: -
// 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:
//
// 1 <= num <= 3999
//
//
class Solution {
public:
string intToRoman(int num) {
vector<string> romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
vector<int> numbers = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string res = "";
for (auto i = 0; i < numbers.size(); ++i) {
while(num - numbers[i] >= 0) {
res += romans[i];
num -= numbers[i];
}
}
return res;
}
};