20 · String Parsing & Expression Evaluation
#12 Integer to Roman
frequently reported atAdobeTCSWalmartMicrosoftAmazonBloomberg
the problem
In plain words
Write an integer num from 1 to 3999 as a standard Roman numeral. The letters are M = 1000, D = 500, C = 100, L = 50, X = 10, V = 5 and I = 1, written from the biggest value to the smallest. Only I, X, C and M may repeat, at most three times in a row. The values 4, 9, 40, 90, 400 and 900 use the subtractive pairs IV, IX, XL, XC, CD and CM.
in num = 3749
out "MMMDCCXLIX"
3000 + 700 + 40 + 9 = MMM + DCC + XL + IX.
in num = 58
out "LVIII"
50 + 5 + 3.
in num = 1994
out "MCMXCIV"
1000 + 900 + 90 + 4 = M + CM + XC + IV.
- 1 ≤ num ≤ 3999
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy choiceString parsing
where this runsExcel's ROMAN() function writes these standard numerals by default; its optional 'form' argument allows shorter, non-standard ones (499 as ID).
Put the six subtractive pairs into the value table next to the seven letters. Then the whole rule is: take the biggest value that fits, again and again.
solutions
From brute force to optimal
Write the number with only the seven letters (4 → IIII, 9 → VIIII), then rewrite the six long runs into subtractive pairs.
- For M, D, C, L, X, V, I: while num ≥ value, append the letter.
- Replace DCCCC → CM, CCCC → CD, LXXXX → XC, XXXX → XL, VIIII → IX, IIII → IV (longer runs first).
At most 18 additive letters, then six replace passes over that short string.
A few short strings, bounded by the 3999 limit.
class Solution { public String intToRoman(int num) { int[] values = {1000, 500, 100, 50, 10, 5, 1}; String[] symbols = {"M", "D", "C", "L", "X", "V", "I"}; StringBuilder sb = new StringBuilder(); for (int k = 0; k < values.length; k++) { while (num >= values[k]) { // purely additive: 4 → IIII, 9 → VIIII sb.append(symbols[k]); num -= values[k]; } } // Then rewrite the six long runs into subtractive pairs (longer patterns first). return sb.toString() .replace("DCCCC", "CM").replace("CCCC", "CD") .replace("LXXXX", "XC").replace("XXXX", "XL") .replace("VIIII", "IX").replace("IIII", "IV"); }}A 13-row table, biggest first: M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I. For each row, append it while it still fits.
- For k = 0..12: while num ≥ VALUES[k]: append SYMBOLS[k], num −= VALUES[k].
- Return the builder's string.
13 rows and at most 15 appended symbols for any input.
Two fixed arrays and a builder of at most 15 characters.
class Solution { // The 7 symbols plus the 6 subtractive pairs, biggest first. private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; private static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; public String intToRoman(int num) { StringBuilder sb = new StringBuilder(); for (int k = 0; k < VALUES.length; k++) { while (num >= VALUES[k]) { // the biggest value that still fits sb.append(SYMBOLS[k]); num -= VALUES[k]; } } return sb.toString(); }}Dry run
Each decimal digit becomes its own piece: thousands, hundreds, tens, ones. Four small tables do the work.
- thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10].
Four array lookups and three concatenations.
Four tables of fixed size.
class Solution { public String intToRoman(int num) { String[] thousands = {"", "M", "MM", "MMM"}; String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; // Each decimal digit is written on its own, so just look it up. return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10]; }}in the room
How to say it in the interview
talk track
- Write the 13-row table first, biggest first, pairs included.
- Say why greedy is safe here: the table holds every building block of a standard numeral, so the biggest that fits is always next.
- Offer the four lookup tables as the even simpler O(1) answer.
traps
- Leaving the pairs out of the table: 4 comes out as IIII.
- A table in ascending order: greedy needs the biggest value first.
what they ask next
Follow-ups
Numbers above 3999?
Standard numerals stop at MMMCMXCIX; bigger ones historically used a bar over a letter (× 1000), which plain text can't show. Excel's ROMAN() also rejects values above 3999.
Write a ₹ amount in Indian words (crore, lakh, thousand, hundred)?
The same greedy table with place values 10⁷, 10⁵, 10³ and 100: divide to get each part's count, write it in words, keep the remainder.
before you submit
Edge cases to test
- Each pair on its own: 4, 9, 40, 90, 400, 900.
- 3888 gives the longest numeral: MMMDCCCLXXXVIII (15 symbols).
- The ends of the range: 1 → "I", 3999 → "MMMCMXCIX".
practise next
Similar problems
- #13Roman to IntegerEasyin Parsing
- #322Coin ChangeMediumin Dynamic Programming
- #66Plus OneEasyin Math & Numbers