Problem Description

You need to convert an integer into its Roman numeral representation.

Roman numerals use seven different symbols with specific values:

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

The conversion follows these rules:

1. Basic Rule: Build the Roman numeral by converting decimal place values from highest to lowest. For most values, repeatedly use the largest possible symbol that doesn't exceed the remaining number.

2. Subtractive Form: When a decimal place value starts with 4 or 9, use a special subtractive notation:

   • 4 → IV (1 before 5)
   • 9 → IX (1 before 10)
   • 40 → XL (10 before 50)
   • 90 → XC (10 before 100)
   • 400 → CD (100 before 500)
   • 900 → CM (100 before 1000)

3. Repetition Limits: Powers of 10 (I, X, C, M) can appear at most 3 times consecutively. The symbols V, L, and D cannot be repeated. If you would need 4 of the same symbol, use the subtractive form instead.

For example:

• 3 → III (three 1's)
• 4 → IV (not IIII)
• 58 → LVIII (50 + 5 + 3)
• 1994 → MCMXCIV (1000 + 900 + 90 + 4)

Given an integer num, return its Roman numeral representation as a string.

Intuition

When converting a number to Roman numerals, we naturally think about how we would do it manually. We'd start with the largest symbols and work our way down, using as many of each symbol as possible before moving to smaller ones.

The key insight is that we need to handle both regular symbols and the special subtractive cases (like 4, 9, 40, 90, 400, 900). Instead of writing complex conditional logic to detect when we need subtractive notation, we can treat these special cases as standalone "symbols" with their own values.

For instance, rather than checking if we have a 4 or 9 pattern, we can simply include IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900) in our list of available symbols alongside the regular ones.

This transforms the problem into a simple greedy algorithm: we create a list of all symbols (including the two-character subtractive forms) ordered by value from largest to smallest. Then we iterate through this list, using each symbol as many times as possible before moving to the next smaller one.

For example, with the number 1994:

• Use M once (1000), leaving 994
• Use CM once (900), leaving 94
• Use XC once (90), leaving 4
• Use IV once (4), leaving 0
• Result: MCMXCIV

This greedy approach works because Roman numeral notation is designed to represent numbers using the fewest symbols possible, always preferring larger values when available. By including the subtractive forms in our symbol list, we ensure they're automatically used when appropriate without any special case handling.

Learn more about Math patterns.

Solution Approach

The implementation uses a greedy algorithm with pre-defined symbol-value pairs. Here's how it works:

Step 1: Define Symbol-Value Mappings

We create two tuples that store all possible Roman numeral representations in descending order by value:

• cs contains the symbols: ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')
• vs contains the values: (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)

Notice how both regular symbols and subtractive forms are included in the same list.

Step 2: Greedy Conversion Process

We initialize an empty list ans to build our result. Then we iterate through each symbol-value pair using zip(cs, vs):

For each pair (c, v):

• While num >= v, we can use this symbol
• Subtract the value v from num
• Append the symbol c to our result list
• Repeat until num is less than the current value

Step 3: Build Final String

After processing all symbols, we join the list of symbols into a single string using ''.join(ans).

Example Walkthrough with num = 58:

• Start with M (1000): 58 < 1000, skip
• Continue through larger values until L (50): 58 >= 50
  • Add 'L', num becomes 8
• Skip values until V (5): 8 >= 5
  • Add 'V', num becomes 3
• Skip to I (1): 3 >= 1
  • Add 'I' three times, num becomes 0
• Result: 'LVIII'

The algorithm's time complexity is O(1) since we have a fixed number of symbols (13), and the space complexity is also O(1) as the maximum length of any Roman numeral within the typical integer range is bounded.

Example Walkthrough

Let's walk through converting the number 94 to Roman numerals using our greedy approach.

Setup: We have our symbol-value pairs ordered from largest to smallest:

• M(1000), CM(900), D(500), CD(400), C(100), XC(90), L(50), XL(40), X(10), IX(9), V(5), IV(4), I(1)

Step-by-step process:

1. Start with num = 94, result = ""

   • Check M(1000): 94 < 1000 → skip
   • Check CM(900): 94 < 900 → skip
   • Check D(500): 94 < 500 → skip
   • Check CD(400): 94 < 400 → skip
   • Check C(100): 94 < 100 → skip

2. Reach XC(90): 94 ≥ 90 ✓

   • Add "XC" to result
   • Subtract 90 from num: 94 - 90 = 4
   • Result = "XC", num = 4

3. Continue with num = 4

   • Check L(50): 4 < 50 → skip
   • Check XL(40): 4 < 40 → skip
   • Check X(10): 4 < 10 → skip
   • Check IX(9): 4 < 9 → skip
   • Check V(5): 4 < 5 → skip

4. Reach IV(4): 4 ≥ 4 ✓

   • Add "IV" to result
   • Subtract 4 from num: 4 - 4 = 0
   • Result = "XCIV", num = 0

5. num = 0, conversion complete

Final answer: "XCIV"

Notice how the algorithm automatically uses the subtractive form XC for 90 and IV for 4, without any special conditional logic. By including these two-character combinations in our symbol list, the greedy approach naturally selects them when appropriate, resulting in the correct and most concise Roman numeral representation.

Solution Implementation

Time and Space Complexity

The time complexity is O(m), where m is the number of symbols (13 in this case). Although there's a nested structure with the for loop and while loop, the total number of iterations across all symbols is bounded. Each unit of the input number can only be "consumed" once - we subtract from num until it reaches 0. Since the maximum input is 3999 (per Roman numeral constraints), and each subtraction reduces num, the total work done is proportional to the number of symbols times a constant factor. Therefore, the time complexity is O(m).

The space complexity is O(m) as well. We store two tuples (cs and vs) each containing m symbols and their corresponding values. The ans list in the worst case could contain multiple copies of symbols, but the total length is still bounded by a constant multiple of m (for example, the number 3888 would produce "MMMDCCCLXXXVIII", which has a length proportional to the number of symbol categories used). The final string created by ''.join(ans) also has space proportional to m. Thus, the space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Handle Subtractive Cases Separately

A common mistake is trying to detect and handle subtractive cases (4, 9, 40, 90, 400, 900) with special conditional logic instead of including them in the mapping.

Problematic Approach:

def intToRoman(self, num: int) -> str:
    result = []
  
    # Wrong: Trying to detect patterns manually
    while num > 0:
        if num >= 1000:
            result.append('M')
            num -= 1000
        elif num >= 900:  # Special case detection
            result.append('CM')
            num -= 900
        elif num >= 500:
            result.append('D')
            num -= 500
        elif num >= 400:  # Another special case
            result.append('CD')
            num -= 400
        # ... many more if-elif statements

This approach leads to:

• Verbose, error-prone code with many conditional branches
• Difficulty maintaining and debugging the logic
• Higher chance of missing edge cases

Solution: Include all subtractive forms directly in the symbol-value mappings and process them uniformly with the greedy algorithm.

2. Using Modulo and Division Instead of Subtraction

Some might try to optimize by calculating how many times each symbol appears using division and modulo operations.

Problematic Approach:

def intToRoman(self, num: int) -> str:
    symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    result = []
  
    for i, value in enumerate(values):
        count = num // value  # How many times this symbol appears
        if count:
            result.append(symbols[i] * count)
            num = num % value  # Wrong: loses track of remaining value

While this might seem cleaner, it:

• Makes the code less intuitive
• Can introduce subtle bugs if not handled carefully
• Doesn't provide significant performance benefits for this problem

Solution: Stick with the simple subtraction approach which is clearer and equally efficient.

3. Incorrect Symbol Ordering

Placing symbols in the wrong order (not strictly descending by value) breaks the greedy algorithm.

Problematic Approach:

# Wrong order - smaller values before larger ones
symbols = ('I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M')
values = (1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000)

This would cause the algorithm to use smaller denominations first, producing incorrect results like using many I's instead of larger symbols.

Solution: Always maintain strict descending order by value in your mappings.

4. String Concatenation Instead of List Building

Using string concatenation in the loop is inefficient in Python.

Problematic Approach:

result = ""  # String instead of list
for symbol, value in zip(roman_symbols, decimal_values):
    while num >= value:
        num -= value
        result += symbol  # String concatenation - inefficient

String concatenation creates a new string object each time, leading to O(n²) time complexity for building the result.

Solution: Use a list to collect symbols and join them at the end with ''.join() for O(n) complexity.