Integer to Roman

Problem

Roman numerals use seven symbols: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Numbers are built by writing symbols from largest value to smallest and concatenating them, with six subtractive forms to avoid four-in-a-row: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Given an integer num, convert it to its Roman numeral string.

Examples

• num = 3 → "III" — three ones.
• num = 58 → "LVIII" — 50 (L) + 5 (V) + 3 (III).
• num = 1994 → "MCMXCIV" — 1000 (M) + 900 (CM) + 90 (XC) + 4 (IV).

Constraints

• 1 <= num <= 3999

Think about it first

TL;DR

Greedily subtract from a descending value-to-symbol table that includes the subtractive pairs. O(1) time and space, since the table and output are bounded.

Approach 1 — Greedy over a value/symbol table

Treat the six subtractive forms (CM, CD, XC, XL, IX, IV) as ordinary entries in a descending value table. Building the numeral is then a single greedy loop: append the largest symbol that still fits and subtract its value. Greedy is correct because the Roman system writes each value with as many high-value symbols as possible.

def intToRoman(num: int) -> str:
    table = [
        (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"),
    ]
    parts = []
    for value, symbol in table:
        if num == 0:
            break
        count, num = divmod(num, value)
        parts.append(symbol * count)
    return "".join(parts)

Walkthrough with num = 1994:

Joining gives "MCMXCIV". (Entries whose value exceeds the remaining num yield count 0 and contribute nothing.)

Complexity: the table has 13 fixed entries and the output is at most ~15 characters, so this is O(1) time and O(1) space in num.

Approach 2 — Per-digit lookup tables

Since num <= 3999, it has at most four decimal digits, and each digit position maps to a small fixed set of numeral strings. Precompute the possibilities for thousands, hundreds, tens, and ones, then index by each digit and concatenate. No loop, and no arithmetic beyond extracting digits.

def intToRoman(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 // 100 % 10]
        + tens[num // 10 % 10]
        + ones[num % 10]
    )

Walkthrough with num = 58: thousands[0] = "", hundreds[0] = "", tens[5] = "L", ones[8] = "VIII" → "LVIII".

Complexity: O(1) time and space — four constant-size table lookups.

Common pitfalls

• Omitting the subtractive pairs from the greedy table; without them you’d emit "IIII" instead of "IV".
• Ordering the table incorrectly — it must be strictly descending by value for the greedy step to be correct.
• In the digit-table version, forgetting the % 10 when extracting the hundreds and tens digits.

Pattern takeaway

When a target notation has a small, fixed set of denominations, greedy largest-first subtraction produces the encoding directly, the same way canonical coin systems make change. Folding the exceptional cases (the subtractive pairs) into the denomination list keeps the loop uniform and free of special-case branches.