Integer to Roman
Convert an integer to a Roman numeral greedily, by putting the subtractive pairs into the value table
Problem Statement
Convert an integer (1 to 3999) into a Roman numeral.
Input: 3 → "III"
Input: 58 → "LVIII" (50 + 5 + 3)
Input: 1994 → "MCMXCIV" (1000 + 900 + 90 + 4)Intuition
Roman numerals are written largest-value-first, so the natural approach is greedy: repeatedly subtract the largest value that still fits, appending its symbol each time.
The complication is subtractive notation — 4 is IV, not IIII, and 900 is CM, not DCCCC. Handling those as exceptions after the fact means a pile of special cases.
The key insight
Treat the subtractive pairs as values in their own right.
Instead of seven symbols, use thirteen entries, sorted descending:
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 → INow plain greedy subtraction produces correct numerals with no special cases at all. CM is simply the symbol whose value is 900.
That is the whole trick: move the complexity from the algorithm into the data.
Why greedy is correct here
Because the table includes the subtractive pairs, the gap between consecutive values is never large enough for a greedy choice to strand you. Taking the largest fitting value always leaves a remainder that the smaller values can express — and it uses the fewest symbols, which is the canonical form.
Watch it run
Approach
Build a descending list of (value, symbol) pairs
Include the six subtractive combinations alongside the seven basic symbols.
For each entry, while it fits into the remainder
Append the symbol and subtract the value. A while rather than an if handles repeats such as III.
Solution
def int_to_roman(num: int) -> str:
"""Convert an integer (1–3999) to its Roman numeral form."""
# Subtractive pairs are included so greedy needs no special cases.
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: list[str] = []
for value, symbol in table:
if num == 0:
break
count, num = divmod(num, value) # how many of this symbol fit
parts.append(symbol * count)
return "".join(parts)The explicit-loop form, which shows the greedy subtraction more literally:
def int_to_roman_loop(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"),
]
result = ""
for value, symbol in table:
while num >= value:
result += symbol
num -= value
return resultThe table must stay sorted descending
Greedy relies on trying the largest value first. Reorder the entries and the output silently becomes wrong — 4 would render as IIII if 1 were tried before 4.
Equally, dropping a subtractive pair does not cause an error; it produces a valid-looking but non-canonical numeral. Both failure modes are silent, so the table deserves a careful read.
Building strings efficiently
Both solutions collect pieces in a list and join once. Repeated result += symbol inside a loop creates a new string each time — O(n²) in the worst case. For a numeral of at most 15 characters it makes no practical difference here, but the habit matters on larger inputs.
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(1)
- Time — the table has a fixed 13 entries, and the result is at most 15 characters (
3888=MMMDCCCLXXXVIII). The work is bounded by a constant regardless of the input value. - Space — the output string, itself bounded by 15 characters.
Edge Cases
Related Problems
- Roman to Integer — the inverse, which compares neighbours instead of subtracting greedily
- Jump Game — greedy choices with a correctness argument
- Candy — greedy applied in more than one direction