algoadvance

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty-seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Clarifying Questions

1. Input Range: Should we handle inputs only within the valid range for Roman numerals (1 to 3999)?
   • Yes, the input will always be within the range from 1 to 3999.
2. Output Format: Should the output be in a string format as a valid Roman numeral?
   • Yes, the output should be a string representing the Roman numeral.
3. Input Validation: Should we account for any invalid inputs like non-integers or values outside the specified range?
   • No, you can assume the input will always be a valid integer within the range.

Strategy

1. Mapping Roman Numerals: Create a list of tuples mapping integers to their respective Roman numeral strings. The list should be ordered from the largest to the smallest to facilitate conversion.
2. Iterate and Convert: Starting from the largest value, subtract the value from the number and append the corresponding Roman numeral until the number is reduced to zero.

Code

def intToRoman(num):
    # Define the mapping of values to Roman numeral symbols
    val_to_roman = [
        (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')
    ]
    
    # Initialize the result string
    roman_numeral = ""
    
    # Convert the number to a Roman numeral
    for val, roman in val_to_roman:
        while num >= val:
            roman_numeral += roman
            num -= val
    
    return roman_numeral

# Example usage
print(intToRoman(1994))  # Output: 'MCMXCIV'

Time Complexity

• Time Complexity: O(1) – The time complexity is constant because the maximum number of iterations (and operations) is fixed due to the input constraint (1 to 3999). The loop will execute a fixed number of operations regardless of the input size.
• Space Complexity: O(1) – The space used by the algorithm is constant as it only uses a fixed amount of extra space for the mapping and result string, regardless of the input size.

This solution is efficient and scales appropriately within the given constraints of the problem.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?