DSA Tracker

Visualize

Integer to Roman

Greedy over a descending table that already holds the subtractive pairs

time O(1)space O(1)

Roman numerals look like a special-case nightmare — sometimes letters add, sometimes one letter subtracts from the next — until you notice that the six subtractive forms (CM, CD, XC, XL, IX, IV) can just be listed as values of their own. Put all thirteen values in one descending table and the rule collapses to: repeatedly take the largest value that still fits and write its symbol. Because 900 and 40 are entries, the greedy choice can never produce an illegal run of four identical letters. The input is capped at 3999, so the loop runs a bounded number of times no matter the value — this is O(1) in both time and space.

Details

Animated on: num = 3749 — write it as a Roman numeral.

Problem:Integer to RomanMedium

Greedy over a descending table that already holds the subtractive pairs

step 1 / 10

num = 3749, output empty. The table is scanned high to low: 1000, 900, 500, 400, ... down to 1. The six subtractive forms (CM, CD, XC, XL, IX, IV) sit IN that table as ordinary entries, which is what stops the greedy pass from ever writing four of the same letter in a row — 40 is reachable directly, so XXXX is never the largest thing that fits.

Pseudocode
1FUNCTION intToRoman(num)
2  VALUES <- [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
3  SYMBOLS <- [M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I]
4  out <- EMPTY
5  FOR i <- 0 TO LENGTH(VALUES) - 1
6    WHILE num >= VALUES[i]
7      APPEND SYMBOLS[i] TO out
8      num <- num - VALUES[i]
9  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. num = 3749, output empty. The table is scanned high to low: 1000, 900, 500, 400, ... down to 1. The six subtractive forms (CM, CD, XC, XL, IX, IV) sit IN that table as ordinary entries, which is what stops the greedy pass from ever writing four of the same letter in a row — 40 is reachable directly, so XXXX is never the largest thing that fits.
  2. 3749 left. Nothing in the table is larger, so 1000 is the biggest bite available. Append "M": output is "M" and 3749 - 1000 = 2749 remains.
  3. 2749 left. The same entry still fits, so it fires again — repetition is how 1000s beyond the first are written. Append "M": output is "MM" and 2749 - 1000 = 1749 remains.
  4. 1749 left. The same entry still fits, so it fires again — repetition is how 1000s beyond the first are written. Append "M": output is "MMM" and 1749 - 1000 = 749 remains.
  5. 749 left. 900 (CM) was the next entry up and needs 900, but only 749 remained — so 500 is the largest value that still fits. Append "D": output is "MMMD" and 749 - 500 = 249 remains.
  6. 249 left. 400 (CD) was the next entry up and needs 400, but only 249 remained — so 100 is the largest value that still fits. Append "C": output is "MMMDC" and 249 - 100 = 149 remains.
  7. 149 left. The same entry still fits, so it fires again — repetition is how 100s beyond the first are written. Append "C": output is "MMMDCC" and 149 - 100 = 49 remains.
  8. 49 left. 50 (L) was the next entry up and needs 50, but only 49 remained — so 40 is the largest value that still fits. "XL" is one symbol, not two letters — it reads as 50 - 10 = 40. Append "XL": output is "MMMDCCXL" and 49 - 40 = 9 remains.
  9. 9 left. 10 (X) was the next entry up and needs 10, but only 9 remained — so 9 is the largest value that still fits. "IX" is one symbol, not two letters — it reads as 10 - 1 = 9. Append "IX": output is "MMMDCCXLIX" and 9 - 9 = 0 remains.
  10. num has reached 0, so every remaining table entry is too big to fire and the loop ends. 3749 is written as "MMMDCCXLIX" in 10 letters. The value never went negative at any point, because each step subtracted a value it had already checked was no larger than what was left.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Integer to Roman in the editorAll Strings problemsBack to roadmap