Integer to Roman

Seven different symbols represent Roman numerals with the following values:

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:
    def intToRoman(self, num: int) -> str:
        roman_map = {
            1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X',
            40: 'XL', 50: 'L', 90: 'XC', 100: 'C',
            400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'
        }
        
        integers = list(roman_map.keys())
        integers.sort(reverse=True)
        
        result = ''
        for i in integers:
            while num >= i:
                result += roman_map[i]
                num -= i
        return result

Explanation:

The problem requires converting an integer to a Roman numeral. The integer will be between 1 and 3999. Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M, each having respective values 1, 5, 10, 50, 100, 500, and 1000.

The approach involves creating a mapping between integer values and their corresponding Roman numeral symbols. The integer values are sorted in descending order. The algorithm iterates through these integer values. For each value, it checks how many times the integer can be subtracted from the input number. The corresponding Roman numeral is appended to the result string for each subtraction. Finally, the result string, which represents the Roman numeral, is returned.

Example:

For num = 3749:

1. Start with num = 3749.
2. The largest value in roman_map is 1000. Subtract 1000 from 3749 three times and append "M" three times. result = "MMM", num = 749.
3. The next largest value is 900, which is less than 749, but is a special subtractive case. 900 doesn't get skipped because the loop iterates through it in descending order. Skip.
4. The next largest value is 500. Subtract 500 from 749 and append "D". result = "MMMD", num = 249.
5. The next largest value is 400. Subtract 400 from 249 and append "CD". result = "MMMDCD", num = 249-400 = -151. This subtractive form is only used once in each decimal place.
6. The next largest value is 100. Subtract 100 from 249 twice and append "CC". result = "MMMDCC", num = 49.
7. The next largest value is 90. Subtract 40 from 49 and append "XL". result = "MMMDCCXL", num = 9.
8. The next largest value is 9. Subtract 9 from 9 and append "IX". result = "MMMDCCXLIX", num = 0.
9. The loop finishes, and the function returns "MMMDCCXLIX".

Big(O) Time Complexity Analysis:

• The time complexity is O(1) because the number of iterations in the loop is limited by the size of the roman_map, which is constant (13 in this case). The while loop also executes a limited number of times, as the integer values in roman_map are fixed.

Big(O) Space Complexity Analysis:

• The space complexity is O(1) because the roman_map and the result string's maximum length are limited and do not depend on the input num. The size of roman_map is constant, and the maximum length of result will be when num is 3888 (MMMDCCCLXXXVIII), which is still a limited constant.

Edge Cases:

1. Input is 1: The output should be "I".
2. Input is 3999: The output should be "MMMCMXCIX".
3. Input contains a 4 or 9 in any decimal place: The output should use the subtractive form (e.g., 4 is "IV", 9 is "IX", 40 is "XL", 90 is "XC", 400 is "CD", 900 is "CM").
4. Input requires multiple repetitions of the same symbol: The algorithm can repeat the I, X, C, and M symbols up to three times.
5. Input is zero or negative: The problem statement specifies that 1 <= num <= 3999, so this case doesn't need to be handled, but in a more general case, error handling should be added for inputs less than one.