Problem Statement

Integer to Roman

Your job is to turn a regular number into a Roman numeral. Romans wrote numbers with seven letters: I means 1, V means 5, X means 10, L means 50, C means 100, D means 500, and M means 1000. There are also six special "one less than" forms where a smaller letter sits in front of a bigger one to mean subtract: IV is 4 (one before five), IX is 9, XL is 40, XC is 90, CD is 400, and CM is 900. The trick we use is called greedy. Greedy means you always grab the biggest piece you can right now and never look back. So we make a list of every value and its symbol, ordered from biggest to smallest, and we keep peeling off the largest chunk that still fits until the number hits 0. For Roman numerals, grabbing the biggest piece first always gives the correct answer, so greedy is exactly the right tool.

mediumMathStringMath & Number TheoryTime: O(1) · Space: O(1)

Signals to notice

integer to Roman numeralgreedy largest-firstinclude subtractive forms in table

Brute force first

Not applicable — greedy IS the natural approach.

The key insight

Table of (value, symbol) including subtractive forms. Greedily subtract largest possible value, append symbol. O(1) since input ≤ 3999.

Trace it on `num = 1994`

start: num=1994, result=""; iterate values descending
val=1000 'M': 1994>=1000 → result="M", num=994; 994<1000 stop
val=900 'CM': 994>=900 → result="MCM", num=94; 94<900 stop
val=500/400/100: 94 < all, skip none appended → result="MCM", num=94
val=90 'XC': 94>=90 → result="MCMXC", num=4; 4<90 stop
val=50/40/10/9/5: 4 < all, skip → result="MCMXC", num=4
val=4 'IV': 4>=4 → result="MCMXCIV", num=0; loop ends
num=0 → return "MCMXCIV"

What must stay true

Including IV, IX, XL, XC, CD, CM in the table means the greedy algorithm handles subtractive notation naturally.

Shape of the loop

values = [(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 (val, symbol) in values:        # descending, includes subtractive forms
    while num >= val:               # greedily take largest that fits
        result += symbol; num -= val
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not including subtractive forms — handling 4, 9, 40, etc. as special cases is much more complex.

Math & Number Theory Pattern