Integer to Roman

Integer to Roman is a classic "build a string from a lookup table" problem. It teaches a clean greedy move: when symbols come in fixed denominations, always grab the largest one that still fits.

The slow way first

You could special-case every digit position — handle thousands, then hundreds, then tens, then ones, each with its own if ladder for the 4/9 subtractive forms. It works, but it is a sprawl of branches that is easy to get wrong, and it does not generalize.

The question to ask: what if I treated the six subtractive forms as real "denominations" too? If CM (900) and IV (4) are just entries in my table alongside M and I, then the whole problem collapses into one greedy loop — no digit logic at all.

The idea: greedily spend the largest denomination

List all 13 value→symbol pairs in descending order, with the subtractive forms (CM, CD, XC, XL, IX, IV) sitting between the plain ones. Then, like making change with the fewest coins: repeatedly take the largest value that is ≤ n, append its symbol, and subtract it. Keep doing that until n reaches 0.

Because the table is sorted descending and includes the subtractive forms, the greedy choice is always correct — there is never a reason to skip a bigger value that fits in favor of a smaller one.

Walk through it

Step through the animation with n = 1994. The pointer p walks the table left to right. At 1000 it fits, so we take M and n drops to 994. At 900 it fits, so we take CM and n drops to 94. We slide past 500, 400, 100 (all too big), take XC at 90 (n → 4), slide past 50 down to 5, then take IV at 4 (n → 0). The result string spells out MCMXCIV.

Pseudocode

pairs = [(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 pairs:            # largest first
    while n >= value:                    # while it still fits
        result = result + symbol         # append the symbol
        n = n - value                    # subtract its value
return result

The Python solution

def int_to_roman(n):
    pairs = [
        (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 pairs:
        while n >= value:
            result += symbol
            n -= value
    return result

• pairs is the lookup table — every plain value plus the six subtractive forms, in descending order.
• result is the string we build up symbol by symbol.
• The for loop visits each denomination once, largest first.
• The inner while n >= value is the greedy heart: as long as the current value fits, we keep appending its symbol and subtracting. (For n = 3000 we append M three times here.)
• When the value no longer fits, the while exits and the for moves to the next, smaller denomination.

Complexity

The loop bounds do not grow with n — the table is a constant 13 entries and the output never exceeds about 15 symbols. So both time and space are O(1) for the constrained input range.

When this pattern shows up

Practice