# Leetcode 12 Solution

https://leetcode.com/problems/integer-to-roman

## Thinking Process

The challenge part of this question is these three rules:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

You can definitely write special logic to handle them. But a much simpler way would be to include them in the symbol list:

``````Symbol       Value
I             1
IV            4
V             5
IX            9
X             10
XL            40
L             50
XC            90
C             100
CD            400
D             500
CM            900
M             1000
``````

After that, we can just try to grab the largest symbol from the list to make the target number. For example, if the target number is 45, we grab a XL first, and then 5 is left, we grab a V. The result is XLV.

## Time & Space Complexity

Assuming `N` is the bit length of the input number

• Time complexity: `O(n)`
• Space complexity: `O(1)`

## Solution

``````class Solution {
public:
string intToRoman(int num) {
vector<pair<int, string>> a;
a.push_back(make_pair(1000, "M"));
a.push_back(make_pair(900, "CM"));
a.push_back(make_pair(500, "D"));
a.push_back(make_pair(400, "CD"));
a.push_back(make_pair(100, "C"));
a.push_back(make_pair(90, "XC"));
a.push_back(make_pair(50, "L"));
a.push_back(make_pair(40, "XL"));
a.push_back(make_pair(10, "X"));
a.push_back(make_pair(9, "IX"));
a.push_back(make_pair(5, "V"));
a.push_back(make_pair(4, "IV"));
a.push_back(make_pair(1, "I"));

string res;
while (num)
{
for (int i = 0; i < a.size(); i++)
{
int cnt = num / a[i].first;
if (cnt == 0)
continue;

for (int j = 0; j < cnt; j++)
res += a[i].second;
num -= cnt * a[i].first;
break;
}
}

return res;
}
};
``````