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)

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)

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