12. Integer to Roman

Convert an integer (1–3999) to a Roman numeral. The whole trick is the lookup table: order the value→symbol pairs descending and include the six subtractive forms (CM, CD, XC, XL, IX, IV) as first-class entries, then greedily subtract.

● MediumMathGreedyHash MapTypeScript

PROBLEM What we're solving

Convert an integer num (1 to 3999) into its Roman numeral string. Roman numerals use I, V, X, L, C, D, M, written largest-to-smallest and summed — except for six subtractive pairs (IV, IX, XL, XC, CD, CM). Example: num = 1994 → "MCMXCIV" (M=1000, CM=900, XC=90, IV=4). Example: num = 58 → "LVIII" (L=50, V=5, III=3).

KEY IDEA Put the subtractive pairs IN the table

Insight → the only reason Roman numerals seem fiddly is the subtractive forms (4=IV, 9=IX, 40=XL, …). Stop special-casing them: list them as ordinary entries in a descending value→symbol table — [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]. Now it's a plain greedy: repeatedly take the largest value that still fits, append its symbol, subtract it, until num hits zero.

RECIPE Build the table, then greedily subtract

0 · Build the table. Two parallel arrays (or a list of pairs) ordered by value descending, with the six subtractive pairs inlined. This is the entire difficulty of the problem.
1 · Sweep largest → smallest. For each entry, while num >= value, you can place that symbol — because the table is sorted, the first entry that fits is always the largest legal one (greedy is optimal here).
2 · Append and subtract. result += symbol then num -= value. Repeat the while-loop so e.g. 30 places X three times.
3 · Stop at zero. When num reaches 0, result is the answer. Because 1 I is in the table, this always terminates.

Classic confusion →trying to detect "is this digit a 4 or a 9?" per decimal place and emitting IV/IX by hand. That works but is bug-prone. Once the subtractive pairs live in the table, there are no special cases — a 4 simply means the 4 IV entry fits and the 5 Vone didn't.

COST Complexity & alternatives

Per-digit hardcoding

O(1)

Map each decimal place (ones/tens/…) to a precomputed string. Fast, but four lookup tables and easy to mis-author.

Greedy subtract

O(1)

One descending table, one greedy loop. Bounded work since num ≤ 3999.

Both are effectively O(1): the table has 13 fixed entries and the answer has at most ~15 characters (e.g. 3888 = MMMDCCCLXXXVIII), so the loop body runs a constant-bounded number of times. Space is O(1) beyond the output string.

Pattern transfer →the "descending value table + greedy take-what-fits" shape is the canonical coin change with a canonical coin system (where greedy is provably optimal). It also mirrors Roman to Integer (the inverse: scan symbols, subtract when a smaller value precedes a larger one) and any number-to-words-style encoding.

RUN IT Greedy subtract: largest symbol that fits, repeat

num =

step 0 / 14

STARTInput: 1994. Walk the value→symbol table from largest to smallest, greedily subtracting the largest value that still fits. The subtractive pairs (CM, CD, XC, XL, IX, IV) are baked into the table.

1function intToRoman(num: number): string {
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 
5▶  let result = '';
6 
7  for (let i = 0; i < values.length; i++) {
8    while (num >= values[i]) {     // largest value that still fits
9      result += symbols[i];        // append its symbol
10      num -= values[i];            // subtract it off
11    }
12  }
13 
14  return result;
15}

tableM1000CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1

State

1994

num (left)

result

remaining valuesymbol appendedresult so farentry too big — skip

slowfast

TYPESCRIPT The solution, annotated

intToRoman.ts
function intToRoman(num: number): string {
  // Table ordered DESC, with subtractive pairs inlined.
  const values  = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];

  let result = '';

  for (let i = 0; i < values.length; i++) {
    while (num >= values[i]) {     // largest value that still fits
      result += symbols[i];        // append its symbol
      num -= values[i];            // subtract it off
    }
  }

  return result;
}

Reading it block by block

Lines 3–4 — the table. Two parallel arrays ordered by value descending, with the subtractive pairs (CM, CD, XC, XL, IX, IV) sitting right next to their non-subtractive neighbours. This table is the whole algorithm.

Line 6 — accumulator. resultstarts empty and only ever grows by appending symbols left to right, so it's already in the correct order.

Line 8 — outer sweep.Iterate the table from the largest value down. Because it's sorted, the first entry whose value fits is guaranteed to be the largest legal symbol — which is exactly what greedy needs.

Lines 9–11 — take what fits. While num >= values[i], append symbols[i] and subtract values[i]. The while (not if) lets a single entry repeat — e.g. 30 emits XXX, 3000 emits MMM.

Line 15 — return. Once the sweep finishes, num is 0 and result holds the full numeral. Having 1 I in the table guarantees the loop always drains num completely.

Complexity → O(1) time and space (beyond the output). The table is a fixed 13 entries and num ≤ 3999, so the total number of appended symbols is bounded by a small constant (≤ 15).

INTERVIEWFollow-ups they'll ask

"Why is greedy correct here?" The Roman value system is canonical: each table entry is large enough that taking the biggest fitting value never forces a worse choice later. (For arbitrary coin systems greedy can fail — this one is designed not to.)
"How would you do Roman → Integer?"Scan left to right; add each symbol's value, but if a symbol's value is less than the one after it, subtract it instead (handles IV, IX, …).
"What about numbers above 3999?"Standard Roman numerals don't cover them; you'd need overlines/vinculum notation or a different convention. State the assumption.
"Could you avoid the subtractive pairs in the table?"Yes, but then you'd special-case each 4 and 9 per decimal place — more code and more edge cases. Inlining them keeps the loop branch-free.

OPTIMAL Math

intToRoman.ts
function intToRoman(num: number): string {
  // Table ordered DESC, with subtractive pairs inlined.
  const values  = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];

  let result = '';

  for (let i = 0; i < values.length; i++) {
    while (num >= values[i]) {     // largest value that still fits
      result += symbols[i];        // append its symbol
      num -= values[i];            // subtract it off
    }
  }

  return result;
}

Complexity → O(1) time and space (beyond the output). The table is a fixed 13 entries and num ≤ 3999, so the total number of appended symbols is bounded by a small constant (≤ 15).

ALT 1 Per-decimal-place lookup tables

O(1) time · O(1) space

Precompute the Roman string for each digit in each place (ones, tens, hundreds, thousands), then concatenate the four lookups.

approach-2.ts
function intToRoman(num: number): string {
  const thousands = ['', 'M', 'MM', 'MMM'];
  const hundreds  = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'];
  const tens      = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'];
  const ones      = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'];

  return (
    thousands[Math.floor(num / 1000)] +
    hundreds[Math.floor(num / 100) % 10] +
    tens[Math.floor(num / 10) % 10] +
    ones[num % 10]
  );
}

Note → Marginally faster (no loop), but it bakes in four hand-authored tables — more to write and more places to make a typo. The greedy single-table version is the one most people remember under pressure.

MNEMONIC The one-liner

"Descending table with the subtractive pairs baked in — then greedily take the biggest that fits."

TRIGGERS When you see _ → reach for _

integer → Roman numeral	descending value→symbol table + greedy subtract
subtractive forms (IV, IX, XL…)	add them as 6 extra table entries
canonical coin system, fewest tokens	greedy take-largest-that-fits
repeat the same symbol (XXX, MMM)	inner while, not if

SKELETON The reusable shape

skeleton.ts
function intToRoman(num: number): string {
  const values  = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
  const symbols = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
  let result = '';
  for (let i = 0; i < values.length; i++) {
    while (num >= values[i]) {
      result += symbols[i];
      num -= values[i];
    }
  }
  return result;
}

FLASHCARDS Tap to flip

What is the single trick that makes Integer→Roman easy?

Put the six subtractive pairs (CM, CD, XC, XL, IX, IV) directly into a descending value→symbol table — then it is plain greedy.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the core trick that removes all special-casing?

QUESTION 02

For num = 1994, what is the output?

QUESTION 03

Why is the inner loop a `while` rather than an `if`?

QUESTION 04

Why is the greedy choice (take the largest value that fits) correct here?

QUESTION 05

What does num = 58 produce?

QUESTION 06

What must be true about the table for the algorithm to work?

QUESTION 07

What is the time complexity?

QUESTION 08

#12 · Integer to RomanConvert an integer to Roman numerals greedily against a value→symbol table that includes the six subtractive pairs (CM, CD, XC, XL, IX, IV): repeatedly subtract the largest value that fits and append its symbol.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Put the subtractive pairs IN the table

RECIPE Build the table, then greedily subtract

COST Complexity & alternatives

RUN IT Greedy subtract: largest symbol that fits, repeat

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Math

ALT 1 Per-decimal-place lookup tables

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _