0012-integer-to-roman

Try it on leetcode

Description

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

Solution(Python)

class Solution:
    def __init__(self):
        self.mapping = [(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') ]

    def intToRoman(self, num: int) -> str:
        # num = 3749
        # 3000 =?  MMM
        # 700 = 500 + 100 + 100 = DCC
        # 40 = XL = 50  - 10
        # 9 = IX = 10 - 9
        # 
        # create hashmap of all values
        # orderelsist = largest to smallest
        # 
        # res 
        # num = 3748
        #  condition: num >0
        #    loop  ordered element
        #       condition num > orderedelement
        #         break
        #   num = 3748  [(1000 , m )  () (500, D)....]
        #  res = ""
        #   3748 > 0
        #     -> loop
        #      3748 >= 1000 
        
        #     -> while 3748 > 1000 
        #           3748 - 1000 = 3
        #         res += M
        #      num = 3728 % 1000 = 728
        #   748 > 0
        #     -> loop
        #       748 > 1000 f
        #       748 > 500 t
        #      while 748 >= 500
        #       748 - 500 = 248
        #
        #       res += 3*D
        #       num = 748 % 500 = 
        #  simple algorith m
        #   while num >= mapped value:
        #       append the reuslt
        #        num -= mapped value

        roman = ''
        while num > 0: # 2749
            for (value, symbol) in self.mapping: 
                while num >= value: # 2749 > 1000
                    roman += symbol # MM
                    num -= value # 2749

        return roman