# 12\_Integer to Roman

\[medium]

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Roman rules:

M = 1000

D = 500

C = 100

L = 50

X = 10

V = 5

I = 1

Special cases to pay attention:

CM = 900

CD = 400

XC = 90

XL = 40

IX = 9

IV = 4

## Idea 1

Store all Roman numerals correspond to each decimal.

Get each number for 4 decimals from input integer, convert each to Roman numerals, concatenate them together as output.

## Complexity 1

* Time: $$O(n)$$
* Space: $$O(1)$$

## Solution 1 (brute force)

```python
def intToRoman(num):
    """
    :type num: int
    :rtype: str
    """
    # define Integer to Roman rules
    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 roman letters for each decimal in the integer
    return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]
```

## Idea 2

Store all important Roman numerals, for 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1.

Loop over these important values, if `num` is larger than or equal to it, add corresponding Roman letter and subtract this value. If `num` is less than it, go to next value. Until `num` equal to 0.

## Pros and Cons

Comparing with solution 1, solution 2 doesn't need to specify all the cases. Solution 1 an solution 2 has similar running time.

## Solution 2 (smart solution, less definition)

```python
def intToRoman(num):
    """
    :type num: int
    :rtype: str
    """

    # define Integer to Roman map
    # why use list instead of dictionary? We want them to be in decending order.
    num_map = [[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']]

    # define output as string
    out = ""

    # main body, loop over num_map
    for number, letter in num_map :
        while num >= number :
            num -= number
            out += letter
    return out
```