Integer to Roman
Convert an integer to a Roman numeral greedily: walk a 13-entry value table, subtraction pairs included, and write each symbol while it fits.
Problem Understanding
Integer to Roman: given an integer from 1 to 3999, return its Roman numeral. Symbols are I 1, V 5, X 10, L 50, C 100, D 500, M 1000, written largest first, with six subtraction pairs: IV 4, IX 9, XL 40, XC 90, CD 400, CM 900.
Example: 1994 returns "MCMXCIV".
The Intuition: Largest Value That Fits
This is a textbook greedy algorithm: at every step take the largest value that still fits, like paying with the largest coin first.
The only trick is the table. Put the subtraction pairs in as values of their own, so it has 13 entries:
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
Then walk it once: while num ≥ value, write the symbol and subtract. For 4 the greedy choice is IV, never IIII. The reverse direction is Roman to Integer.
Interactive Walkthrough
The 13-entry table is on top, with the value being tried filled; the numeral grows below it. Try Longest to watch the same value taken several times in a row.
Dry Run Table
Input: num = 1994
| Value tried | Fits? | Written | num after |
|---|---|---|---|
| 1000 M | yes | M | 994 |
| 900 CM | yes | CM | 94 |
| 500 … 100 | no | — | 94 |
| 90 XC | yes | XC | 4 |
| 50 … 5 | no | — | 4 |
| 4 IV | yes | IV | 0 |
Answer: "MCMXCIV".
The Solution Template
Two parallel arrays for the table and a greedy loop.
Integer to Roman Code
1var intToRoman = function(num) {2 const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];3 const symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];4 let out = '';5 for (let i = 0; i < values.length; i++) {6 while (num >= values[i]) {7 out += symbols[i];8 num -= values[i];9 }10 }11 return out;12};
Edge Cases & Common Mistakes
- Leaving out the subtraction pairs: produces
IIIIandDCCCC, which are not valid. - Using
ifinstead ofwhile: values likeMorIcan repeat up to three times. - Wrong table order: the table must be sorted from largest to smallest, with
CMbetweenMandD. - Buffer size in C: the longest numeral, 3888, has 15 characters; allocate at least 16 bytes.
- Digit-by-digit lookup: an alternative is four lookup tables (thousands, hundreds, tens, ones) indexed by each digit; same O(1).
Summary
List the 13 Roman values, subtraction pairs included, from largest to smallest. Walk the list and, while the number is at least the current value, append its symbol and subtract. O(1) time and space for inputs up to 3999.
More practice: DSA interview questions with answers · patterns cheat sheet