Skip to main content

12. Integer to Roman

medium

Convert an integer in [1, 3999] into a Roman numeral string. The standard interview answer uses a greedy table that includes the subtractive forms (IV, IX, XL, XC, CD, CM) as first-class entries.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M with values 1, 5, 10, 50, 100, 500 and 1000. Given an integer, convert it to a roman numeral.

Constraints

  • 1 <= num <= 3999

Examples

Example 1

Input
num = 3
Output
"III"

Explanation: 3 is represented as 3 ones.

Example 2

Input
num = 58
Output
"LVIII"

Explanation: L = 50, V = 5, III = 3.

Example 3

Input
num = 1994
Output
"MCMXCIV"

Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive approach hits special cases (4, 9, 40, 90, 400, 900) ugly.

Hint 2

Build a value-symbol table that INCLUDES the subtractive forms as full 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')]. Now it's pure greedy.

Hint 3

Walk the table top-down. While num >= value, append the symbol and subtract value. Move to the next entry when num < value.

Hint 4

Since the table is descending and each subtractive form is between two regular forms, the greedy is correct.

Solution approach

Reveal approach

Use a descending value-symbol table that includes the subtractive forms (1000,900,500,400,100,90,50,40,10,9,5,4,1 paired with M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I). Walk the table: while num >= value, append the symbol to the result and subtract value from num; otherwise move to the next entry. Because the table is descending and the subtractive forms are interleaved at the correct positions, greedy is provably optimal — you never need to undo a choice. O(1) time and space since the table is constant and num <= 3999 caps the output length at 15.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • math
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg
  • Apple

More Math practice problems

See all Math problems →