Python problem 24 of 30

Roman numerals

Python
Medium

Write to_roman(n) that converts a whole number from 1 to 3999 into Roman numerals.

to_roman(4)      # "IV"
to_roman(1994)   # "MCMXCIV"
to_roman(2026)   # "MMXXVI"

Show hint

Include the subtractive pairs (CM, CD, XC, XL, IX, IV) in your table of values. Then always take the largest value that still fits.

Show solution

def to_roman(n):
    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"),
    ]
    out = ""
    for value, letters in table:
        while n >= value:
            out += letters
            n -= value
    return out

This is a greedy algorithm: at each step take the biggest symbol that fits. Greedy only works because the table includes the special pairs like 900 and 4. Without them, 4 would come out as "IIII". Making change with coins works the same way.

Want a problem like this every day? See today's problem and keep a streak going.