Integer to Roman

Medium#12biggest piece first

Write a whole number from 1 to 3999 in Roman numerals. I, V, X, L, C, D and M are 1, 5, 10, 50, 100, 500 and 1000, written from the biggest down and added up. A symbol may repeat at most three times; for 4, 9, 40, 90, 400 and 900 a smaller symbol goes before a bigger one and is taken away: IV, IX, XL, XC, CD, CM. Our example: 2894 — the answer is "MMDCCCXCIV".

12 Integer to RomanWalkthrough · 1×

Example: 2894. On top is the table from the biggest value down, the subtracted pairs among the plain symbols; below, what is left of num and the symbols written so far.

1000M900CM500D400CD100C90XC50L40XL10X9IX5V4IV1Inum2894out—
not tried yetvalue being trieduseddid not fit

Nothing written yet; num = 2894

01/52
restart · back · play · step
Speed
1function intToRoman(num):
2 out = ""
3 for each (value, symbol) in table: // 1000 M, 900 CM, 500 D, 400 CD, …, 4 IV, 1 I
4 while num >= value:
5 out = out + symbol
6 num = num - value
7 return out
state
num
2894
out
""
value
–
symbol
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. With only the symbols below a value, a correct numeral stays under that value: below CM = 900 the most is DCCCXCIX = 899. So when a value fits, the numeral has to take it now; the smaller ones cannot make it up.
  2. The pairs CM, CD, XC, XL, IX and IV are in the table as values of their own. Thanks to them greed never needs four of a kind: 94 becomes XC + IV, not LXXXX + IIII.
  3. num only shrinks, and the table is walked once from the top, so the symbols come out from the biggest down, as Roman numerals require.

Complexity

Time O(1): the table has 13 values, and no symbol is written more than three times in a row, so at most 15 symbols come out. Memory O(1) besides the answer.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.