Integer to Roman

Difficulty: Medium | Acceptance: 69.22% | Paid: No

Topics: Hash Table, Math, String

• Examples
• Constraints
• Brute Force Approach
• Digit-by-Digit Approach
• Greedy Subtraction

Examples

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

Input

num = 58

Output

"LVIII"

Explanation

50 = L 8 = VIII

Input

num = 1994

Output

"MCMXCIV"

Explanation

1000 = M 900 = CM 90 = XC 4 = IV

Constraints

- 1 <= num <= 3999

Brute Force Approach

Intuition

The basic idea is to use the largest value Roman numeral symbols first and subtract them from the number until it’s zero. We need to handle special subtractive cases like IV, IX, XL, XC, CD, CM explicitly.

Steps

• Identify all valid Roman numeral combinations in descending order of their values, including both regular symbols and subtractive cases.
• Iterate through these values, subtracting the largest possible value from the number and appending the corresponding Roman symbol to the result string.
• Repeat until the input number becomes zero.

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the mapping from integer values to Roman numeral strings
        # Including both regular symbols and subtractive cases like 4, 9, 40, 90, 400, 900
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        numerals = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        
        result = []
        
        # Process each value from the highest to the lowest
        for i in range(len(values)):
            # While the current value can be subtracted from num
            while num >= values[i]:
                num -= values[i]
                result.append(numerals[i])
        
        # Join the list into a single string and return
        return ''.join(result)

Complexity

• Time: O(1) - Since there are a fixed number of iterations based on the limited input range (max 3999), we can consider it constant time.
• Space: O(1) - We only use a fixed amount of extra space regardless of the input size.
• Notes: This is often considered O(1) because the number of operations is bounded by a constant, not dependent on the input size in the asymptotic sense.

Digit-by-Digit Approach

Intuition

Instead of processing the whole number, we can process it digit by digit, starting from thousands down to units. For each digit, we can use a lookup table to get the corresponding Roman numeral part.

Steps

• Break the number into its digits (thousands, hundreds, tens, units).
• Create lookup tables for each digit place that map numbers 0-9 to their Roman numeral equivalents, considering subtractive forms.
• Build the result string by concatenating the Roman numeral parts for each digit.

class Solution:
    def intToRoman(self, num: int) -> str:
        # Lookup tables for each digit place
        thousands = ["", "M", "MM", "MMM"]
        hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        units = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        
        # Extract each digit and use lookup tables
        return (thousands[num // 1000] + 
                hundreds[(num % 1000) // 100] + 
                tens[(num % 100) // 10] + 
                units[num % 10])

Complexity

• Time: O(1) - As the number of operations is constant and independent of the input value.
• Space: O(1) - We use a fixed-size lookup table, so the space complexity is constant.
• Notes: This approach is very efficient since it directly computes the result without looping. It’s a classic example of trading space for time.

Greedy Subtraction

Intuition

This is a greedy algorithm where at each step we subtract the largest possible Roman numeral value. It’s similar to the brute force but emphasizes that we’re making a locally optimal choice at each step.

Steps

• Create a list of value-symbol pairs in descending order, including subtractive cases.
• Iterate through this list, and for each pair, repeatedly subtract the value from the number and append the symbol to the result as long as the value is less than or equal to the current number.
• Continue until the number becomes zero.

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the value-symbol pairs in descending order
        value_symbols = [
            (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")
        ]
        
        result = []
        
        # Process each pair from the largest to the smallest
        for value, symbol in value_symbols:
            # Add the symbol while the value can be subtracted from num
            count = num // value
            if count:
                result.append(symbol * count)
                num -= value * count
                
        # Join the list into a single string and return
        return ''.join(result)

Complexity

• Time: O(1) - The number of operations is bounded by a constant due to the fixed input range.
• Space: O(1) - We use a fixed amount of extra space regardless of the input size.
• Notes: This is essentially the same as the brute force approach, but framed as a greedy algorithm.