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. For example:

• 3749 becomes MMMDCCXLIX (3000 = MMM, 700 = DCC, 40 = XL, 9 = IX)
• 58 becomes LVIII (50 = L, 8 = VIII)
• 1994 becomes MCMXCIV (1000 = M, 900 = CM, 90 = XC, 4 = IV)

Write a program to implement this conversion, keeping in mind the 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 code converts an integer to a Roman numeral using a greedy approach. It defines a dictionary roman_map that maps integer values to their corresponding Roman numeral symbols. The algorithm iterates through the integers in descending order. For each integer, it checks how many times it can be subtracted from the input number. If the integer can be subtracted, the corresponding Roman numeral symbol is appended to the result string, and the input number is reduced by the integer value. The process repeats until the input number becomes zero, at which point the generated Roman numeral string is returned.

Example:

For the input num = 3749:

1. Start with result = ''.
2. Iterate through integers in descending order.
3. For i = 1000, num >= 1000 is true, so result += 'M' and num = 2749.
4. Repeat step 3 twice more until num = 749 and result = 'MMM'.
5. For i = 500, num >= 500 is true, so result += 'D' and num = 249.
6. For i = 400, num >= 400 is false.
7. For i = 100, num >= 100 is true, so result += 'C' and num = 149.
8. Repeat step 7 once more until num = 49 and result = 'MMDCC'.
9. For i = 40, num >= 40 is true, so result += 'XL' and num = 9.
10. For i = 9, num >= 9 is true, so result += 'IX' and num = 0.
11. The loop terminates, and the function returns MMMDCCXLIX.

Brute Force Solution:

A brute-force solution would involve a series of if and elif statements to check the value of num and repeatedly subtract from it. This approach would be less efficient and more difficult to read.

class Solution:
    def intToRoman(self, num: int) -> str:
        result = ''
        while num > 0:
            if num >= 1000:
                result += 'M'
                num -= 1000
            elif num >= 900:
                result += 'CM'
                num -= 900
            elif num >= 500:
                result += 'D'
                num -= 500
            elif num >= 400:
                result += 'CD'
                num -= 400
            elif num >= 100:
                result += 'C'
                num -= 100
            elif num >= 90:
                result += 'XC'
                num -= 90
            elif num >= 50:
                result += 'L'
                num -= 50
            elif num >= 40:
                result += 'XL'
                num -= 40
            elif num >= 10:
                result += 'X'
                num -= 10
            elif num >= 9:
                result += 'IX'
                num -= 9
            elif num >= 5:
                result += 'V'
                num -= 5
            elif num >= 4:
                result += 'IV'
                num -= 4
            else:
                result += 'I'
                num -= 1
        return result

Time Complexity: O(1)

The time complexity is constant, O(1), because the maximum number of iterations is limited by the range of the input (1 to 3999). The loop iterates at most a few times for each Roman numeral symbol, and the number of symbols is fixed.

Space Complexity: O(1)

The space complexity is constant, O(1), as the space used by the roman_map dictionary and the result string is fixed regardless of the input value. The dictionary has a fixed number of key-value pairs, and the length of the result string is limited by the maximum possible length of a Roman numeral representation (for 3888, it would be MMMDCCCLXXXVIII).

Edge Cases:

1. Input 1: The algorithm correctly handles the input 1 and returns "I".
2. Input 3999: The algorithm correctly handles the input 3999 and returns "MMMCMXCIX".
3. Input near boundaries (e.g., 4, 9, 14, 39): The subtractive forms are correctly handled for numbers like 4 ("IV"), 9 ("IX"), 40 ("XL"), and 90 ("XC").
4. Zero and Negative Inputs: The constraints specify that the input will be between 1 and 3999. If zero or negative inputs were allowed, the code would need to be modified to handle these cases gracefully, possibly by returning an empty string or raising an exception.