Roman Numeral Conversion

Problem

Given an integer, convert it to a Roman numeral.

Naive Approach

The most straightforward approach is to iterate through the decimal place values (1000, 100, 10, 1) and greedily subtract the largest possible Roman numeral value from the input number until the number becomes zero. This method uses a series of if or while statements to check each possible value and append the corresponding Roman numeral symbol.

Optimal Approach

A more efficient and cleaner approach is to use a lookup table (array or dictionary) that maps integer values to their Roman numeral representations. This allows us to iterate through the values in descending order and avoid repetitive checks. The lookup table should include the standard Roman numeral values (1, 5, 10, 50, 100, 500, 1000) as well as the subtractive forms (4, 9, 40, 90, 400, 900).

1. Create two arrays: one for integer values (e.g., values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]) and another for their corresponding Roman numeral symbols (e.g., symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]).
2. Iterate through the values array from highest to lowest.
3. For each value, determine how many times it can be subtracted from the input number.
4. Append the corresponding Roman numeral symbol to the result string that many times.
5. Subtract the value multiplied by the number of times it was used from the input number.
6. Repeat until the input number becomes zero.

Example

Convert 1994 to a Roman numeral:

• 1000: Append "M", number becomes 994
• 900: Append "CM", number becomes 94
• 90: Append "XC", number becomes 4
• 4: Append "IV", number becomes 0

Result: "MCMXCIV"

Code

def int_to_roman(num: int) -> str:
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    
    roman_numeral = ""
    i = 0
    
    while num > 0:
        k = num // values[i]
        
        for _ in range(k):
            roman_numeral += symbols[i]
            num -= values[i]
        
        i += 1
        
    return roman_numeral

Big O Analysis

• Time Complexity: O(1) - The algorithm iterates through a fixed number of values (13 in this case), regardless of the input number. The number of iterations is constant.
• Space Complexity: O(1) - The algorithm uses a fixed amount of space for the values and symbols arrays, regardless of the input number. The result string also has a limited length because the input number is constrained to be between 1 and 3999.

Edge Cases

• Input number is 1: Should return "I".
• Input number is 3999: Should return "MMMCMXCIX".
• Input number is a multiple of 10: (e.g., 10, 100, 1000) - Should return "X", "C", "M" respectively.
• Input number contains subtractive forms: (e.g., 4, 9, 40, 90, 400, 900) - Should return "IV", "IX", "XL", "XC", "CD", "CM" respectively.