Integer to Roman

The code is short. The trap is assuming the rules are short enough for a pile of special cases.

A reliable Integer to Roman solution treats Roman notation as a finite, ordered set of legal tokens. Scan those tokens from largest to smallest, repeatedly emit the largest token that fits, and stop when the remainder reaches zero.

The contract and the key observation

The input is an integer from 1 through 3999. The output must be its canonical Roman-numeral representation using these seven basic symbols:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are built by converting decimal place values from highest to lowest. Most values use ordinary symbols:

• 3 becomes III
• 70 becomes LXX
• 800 becomes DCCC

Six values use subtractive tokens:

Value	Token
4	IV
9	IX
40	XL
90	XC
400	CD
900	CM

These tokens must be treated as complete choices. If the remainder is 9, the algorithm should choose IX, not produce nine I characters or invent another subtraction.

The central idea is simple:

Store every legal token in descending value order. For each token, repeatedly use it while it fits.

That table carries most of the problem's rules. The loop only consumes the number.

Recognize the greedy structure

This is a greedy problem because each step chooses the largest legal token that fits the current remainder.

The recognition cues are unusually clean:

• The set of legal tokens is finite.
• The tokens have a natural descending order.
• The input is bounded.
• Choosing the largest fitting token preserves the required place-value structure.
• The remaining work has the same shape as the original work.

A case-by-case solution can also work. You could inspect the thousands digit, then the hundreds digit, then the tens digit, then the ones digit. But that approach spreads the same rule across several branches. It is easy to miss one of IV, IX, XL, XC, CD, or CM.

The table-driven approach exposes the structure instead of hiding it.

Think of the algorithm as a controlled reduction:

1. Choose the largest legal token that fits.
2. Append that token.
3. Subtract its value.
4. Solve the smaller remainder using the same ordered choices.

For example, when the remainder is 49, the largest fitting token is XL, leaving 9. The next token is IX, so the result is XLIX.

The tempting output IL has the right arithmetic value, but it violates the place-value rules. Greedy choice alone is not enough; the choices must come from the legal token table.

Build the descending token table

The complete table is:

Value	Token
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

The order is a correctness condition, not a cosmetic preference.

Suppose the remainder is 900. If C appeared before CM, the algorithm could emit C and continue. That would consume part of the hundreds place before considering the legal subtractive token. By placing CM first, the table gives the canonical choice priority.

The same logic handles every place value. For 3749:

• 3000 becomes MMM
• 700 becomes DCC
• 40 becomes XL
• 9 becomes IX

So the final representation is MMMDCCXLIX.

Notice the role of place value. The number 49 is 40 + 9, which gives XLIX. It is not 50 - 1, so IL is not a permitted representation. The table encodes this boundary directly: XL and IX exist; IL does not.

This is the useful form of greedy digit mapping: do not ask the algorithm to invent legal combinations. Give it the legal combinations, in the order that defines the canonical output.

Derive the loop and its invariant

The algorithm needs only two pieces of mutable state:

• remaining: the part of the input not yet represented
• result: the Roman fragments already emitted

For each (value, token) pair in the table:

• While value fits into remaining, append token.
• Subtract value from remaining.
• Move to the next, smaller table entry.

The invariant is:

The fragments in result represent the value already consumed. remaining equals the original input minus that consumed value. Every table entry before the current one has been exhausted.

That invariant gives us a clear debugging method. After every subtraction, ask:

• Did the output fragment match the value removed?
• Did the remainder decrease by exactly that value?
• Have all larger tokens already been considered as much as possible?

The while loop matters because ordinary symbols may repeat. 3000 needs three uses of M; 800 needs one D and three uses of C; 8 needs V followed by three I symbols.

The subtractive tokens need no separate branch. CM is simply a token worth 900, and IV is simply a token worth 4. Data handles the special cases. Control flow stays ordinary.

Prove validity and canonicality

There are two different claims to prove.

The result has the correct value

Whenever the algorithm appends a token, it subtracts that token's value from remaining. The fragments therefore account for exactly the amount removed.

The input is positive, and every subtraction uses a positive token that fits. The remainder decreases until it reaches zero. At that point, the emitted fragments add up to the original input.

That proves numerical validity.

The result follows the Roman-numeral contract

Numerical validity alone would allow forbidden forms. For example, a hypothetical table containing IL could still produce the value 49, but it would not produce canonical Roman notation.

Canonicality comes from two properties of the table:

1. It contains only permitted ordinary and subtractive tokens.
2. It is ordered from largest value to smallest value.

At each step, the algorithm selects the largest legal token that fits. It cannot choose I before IV, because IV appears earlier. It cannot choose C before CM, because CM appears earlier.

The table also prevents invalid repetition:

• V, L, and D appear as tokens but never need to repeat.
• I, X, C, and M can repeat only as the remaining place-value structure permits.
• A value that would require a fourth consecutive I, X, or C is handled by a subtractive token such as IV, XL, or CD.

So the greedy choice is safe because it is constrained by the representation system. “Take the biggest number” is too vague. The precise rule is:

Take the largest legal token that fits, where legality and order are defined by the table.

Dry run: 1994 and 58

For 1994, the useful selections are:

Remainder before	Selected token	Remainder after	Output
1994	M	994	M
994	CM	94	MCM
94	XC	4	MCMXC
4	IV	0	MCMXCIV

The algorithm reaches zero without any special condition for 900, 90, or 4. Those cases are already represented in the table.

For 58, the scan selects:

1. L for 50, leaving 8
2. V for 5, leaving 3
3. I three times, leaving 0

The output is LVIII.

The contrast is useful. The same loop handles both subtractive tokens and repeated ordinary symbols. The difference lives in the data, not in a growing network of branches.

Python implementation

def int_to_roman(num: int) -> str:
    # Keep tokens in descending value order.
    tokens = [
        (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 tokens:
        # Use the current token as many times as it fits.
        while num >= value:
            result.append(symbol)
            num -= value

    return "".join(result)

The list is deliberate. Appending fragments makes the state visible, and "".join(result) assembles the final string once at the end. For this bounded problem, repeated string concatenation would still be small, but the list makes the accumulation model easier to inspect.

The code assumes the stated input range. That is the interview contract, so unrelated validation would distract from the algorithm. If the surrounding application accepts arbitrary integers, input policy becomes a separate design decision; it is not part of this conversion loop.

I would choose this table-driven version over nested conditionals or a recursive chain in an interview. The rules are visible in one place, the order is inspectable, and a missing or misplaced token is easy to diagnose.

Complexity and boundary checks

The table has 13 entries. For the stated range, the scan is constant with respect to the input domain. The output length is also bounded because the largest input is 3999.

More generally, if k is the length of the Roman output, the work is proportional to the fixed table scan plus the number of emitted fragments:

• Time: O(1) for the bounded problem, or O(k) when output construction is made explicit
• Space: O(k) for the result list, excluding the returned string

Check the boundaries and the places where representation rules usually break:

• 1 → I
• 4 → IV
• 9 → IX
• 40 → XL
• 90 → XC
• 400 → CD
• 900 → CM
• 49 → XLIX, not IL
• 101 → CI
• 1005 → MV
• 3999 → MMMCMXCIX

The zero-place examples matter. In 101, there is no tens token to emit. In 1005, there are no hundreds or tens tokens. The descending scan simply skips entries that do not fit and continues.

When reviewing an implementation, verify these structural rules:

• Only IV, IX, XL, XC, CD, and CM are used subtractively.
• V, L, and D are never repeated.
• I, X, C, and M are not emitted more than three times consecutively.
• The table is strictly descending.
• The loop stops with num == 0.
• The output is assembled in the same order tokens were selected.

The transferable rule is worth keeping: when a bounded representation system gives you a finite ordered set of legal tokens, and the largest fitting token preserves the canonical form, encode the rules in the table and let the invariant drive the loop.

In an interview, state the table, explain why its order matters, name the remainder invariant, then test the subtractive boundaries. The code will be short because the reasoning did the real work.