Integer to Roman — Solution

Problem

Given an integer between 1 and 3999, convert it to its Roman numeral representation. Roman numerals use seven symbols (I, V, X, L, C, D, M) along with a subtractive notation for six special cases — for example, 4 is written IV rather than IIII.

• Input: num = 1994
• Output: "MCMXCIV"
• Explanation: 1994 = 1000 (M) + 900 (CM) + 90 (XC) + 4 (IV)

Counter-example: num = 1400 → "MCD" (not "MCCCC"), because 400 uses the subtractive form CD.

Intuition

Roman numeral conversion is inherently greedy: always pick the largest symbol that fits into the remaining value. The six subtractive forms (IV, IX, XL, XC, CD, CM) look like special cases, but they're just additional entries in the symbol table. Once you include all 13 symbol-value pairs in descending order, the same greedy loop handles everything uniformly — no branching required.

Solution — Greedy Symbol Table

Build a lookup table of all 13 (value, symbol) pairs ordered from largest (1000) to smallest (1), including the six subtractive pairs. Repeatedly peel off the largest symbol that fits.

1. Define 13 pairs: the seven standard symbols plus the six subtractive forms (900 → CM, 400 → CD, 90 → XC, 40 → XL, 9 → IX, 4 → IV).
2. For each pair in order, while the remaining number is ≥ the value, append the symbol and subtract the value.
3. Return the accumulated string.

1def int_to_roman(num: int) -> str:
2    symbol_table = [
3        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
4        (100,  "C"), (90,  "XC"), (50,  "L"), (40,  "XL"),
5        (10,   "X"), (9,   "IX"), (5,   "V"), (4,   "IV"),
6        (1,    "I"),
7    ]
8    result = []
9    for value, symbol in symbol_table:
10        while num >= value:          # peel off as many copies of this symbol as fit
11            result.append(symbol)
12            num -= value
13    return "".join(result)

Time: O(1) — the loop runs a bounded number of iterations since num ≤ 3999 and each symbol subtracts at least 1. Space: O(1) — the result string length is bounded (at most ~15 characters, e.g. "MMMDCCCLXXXVIII" for 3888).

Complexity Summary

Common Mistakes

• Omitting the subtractive pairs from the table — writing separate if-else branches for IV, IX, XL, XC, CD, CM instead of including them as entries; this produces incorrect output for inputs like 4, 9, 40, 90, 400, and 900.
• Getting the table order wrong — the pair (900, "CM") must appear before (500, "D") so the greedy loop always picks the largest symbol first; an out-of-order table produces wrong results like "DCD" instead of "CM" for 900.
• Forgetting CD (400) or XL (40) — programmers commonly recall IV, IX, XC, and CM but miss the two middle subtractive forms, causing errors for inputs like 1400 or 1440.
• Using string concatenation in a loop in Java — result = result + symbol allocates a new String on every iteration; use StringBuilder.append() to avoid quadratic allocations.
• Adding a guard for num = 0 — the problem guarantees 1 ≤ num ≤ 3999, so a zero check is unnecessary dead code.

Related Problems

• Roman to Integer — inverse conversion; uses the same symbol table in reverse
• Add Binary — string construction from a different numeric base
• Multiply Strings — producing a string result from integer operations without built-in conversion
• Reverse Integer — working with individual digits of a bounded integer
• Largest Number — greedy ordering to build an optimal string representation from numbers