12. Integer to Roman - Explanation

Problem Link

Description

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

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.

You are given an integer, convert it to a Roman numeral.

Example 1:

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

Example 2:

Input: num = 1994

Output: "MCMXCIV"

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

Constraints:

  • 1 <= num <= 3999


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Math - I

Intuition

Roman numerals are built by combining symbols that represent specific values. The key insight is to process values from largest to smallest, repeatedly subtracting the largest possible value and appending its symbol. We include the subtractive combinations (like IV for 4, IX for 9) in our value list to handle them naturally.

Algorithm

  1. Create a list of symbol-value pairs in ascending order, including subtractive forms (IV, IX, XL, XC, CD, CM).
  2. Iterate through the list from largest to smallest value.
  3. For each pair, divide the remaining number by the value to get the count.
  4. Append the symbol count times to the result and update the number using modulo.
  5. Return the resulting Roman numeral string.
class Solution:
    def intToRoman(self, num: int) -> str:
        symList = [
            ["I", 1], ["IV", 4], ["V", 5], ["IX", 9],
            ["X", 10], ["XL", 40], ["L", 50], ["XC", 90],
            ["C", 100], ["CD", 400], ["D", 500], ["CM", 900],
            ["M", 1000]
        ]

        res = ""
        for sym, val in reversed(symList):
            count = num // val
            if count:
                res += sym * count
                num %= val

        return res

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)

2. Math - II

Intuition

Since the input is constrained to 1-3999, we can precompute all possible Roman representations for each digit place (ones, tens, hundreds, thousands). Then we simply look up each digit and concatenate the results. This trades space for simplicity and speed.

Algorithm

  1. Create four arrays containing Roman representations for:
    • Thousands: "", "M", "MM", "MMM"
    • Hundreds: "", "C", "CC", ... "CM"
    • Tens: "", "X", "XX", ... "XC"
    • Ones: "", "I", "II", ... "IX"
  2. Extract each digit using division and modulo.
  3. Look up the corresponding string from each array.
  4. Concatenate and return the result.
class Solution:
    def intToRoman(self, num: int) -> str:
        thousands = ["", "M", "MM", "MMM"]
        hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

        return (
            thousands[num // 1000] +
            hundreds[(num % 1000) // 100] +
            tens[(num % 100) // 10] +
            ones[num % 10]
        )

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)