Integer to Roman
Convert an integer to its Roman numeral representation.
- 1 <= num <= 3999
Intuition
Integer to roman converts a number into Roman numerals. Roman notation is nearly additive — symbols run largest to smallest and sum — except for six subtractive pairs like IV for 4 and CM for 900.
Treating those pairs as special cases produces sprawling conditional code. The clean solution removes the exception entirely:
- Include the six subtractive forms as values in the symbol table, so CM (900) and IV (4) are ordinary entries alongside M and I.
With 13 entries sorted descending — 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 — the algorithm becomes purely greedy: repeatedly append the largest symbol that fits and subtract its value.
The greedy is provably correct here, unlike greedy coin change in general. Roman values are constructed so that taking the largest applicable symbol is always optimal, which is exactly why the subtractive forms exist as distinct entries.
The ordering of the table is load-bearing. If 900 came after 500, the algorithm would emit DCCCC rather than CM, which is valid arithmetic but not valid notation.
A while rather than an if at each entry handles repetition: 3000 emits MMM by applying 1000 three times before advancing.
The constraints cap input at 3999, which is why no symbol above M is needed — larger numerals require overline notation the problem excludes.
Roman to Integer is the reverse direction, where the subtractive pairs are detected by comparing each symbol with the one after it.
Put the six subtractive forms into the value table as if they were symbols, and the whole problem becomes a plain greedy: repeatedly take the largest value that fits. The table's descending order is what makes greedy optimal here.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(1) time and O(1) space.
Absorb the exceptions into the table
Include the six subtractive forms as entries — CM is simply 900 and IV is 4. This removes every special case from the logic.
Sort the table descending
List all 13 values from 1000 down to 1. The ordering is load-bearing: placing 900 after 500 would emit DCCCC instead of CM.
Take the largest fitting symbol
Repeatedly append the largest value not exceeding the remainder and subtract it. The greedy is provably optimal for this table.
Loop rather than branch
Use while at each entry so 3000 emits MMM by applying 1000 three times before moving on. An if would emit only one.
Rely on the input bound
Values are capped at 3999, so no symbol above M is required — larger numerals need overline notation the problem excludes.
Cost of the conversion
The table has fixed size and each symbol repeats at most three times, giving O(1) time and space for the bounded input range.
Solution & live demo
Common pitfalls
Omitting the subtractive pairs from the table
table = [(1000,'M'), (500,'D'), (100,'C'), ...]
table = [(1000,'M'), (900,'CM'), (500,'D'), (400,'CD'), ...]
Without them, 4 renders as "IIII" and 9 as "VIIII" — valid arithmetic but not valid Roman numerals. Treating CM and IV as ordinary table entries handles every case with no special branch.
Using if instead of while
if num >= value:
num -= value
result.append(symbol)while num >= value:
A symbol can repeat up to three times — 3000 is "MMM". Taking each value at most once truncates every number needing repetition.
Building the table out of order
table = [(1,'I'), (4,'IV'), (5,'V'), ...]
# strictly descending by value
Greedy only produces the shortest valid numeral if the largest usable value is always taken first. Ascending order emits a string of Is and never reaches the larger symbols.
Edge cases
Matched directly by the IV or IX table entry, no special-case code needed.
Greedily consumes M three times, then CM, XC, IX in sequence: MMMCMXCIX.
Matches the last table entry, I, directly.
The while loop inside one table entry fires three times in a row, appending MMM.