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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Integer to Roman and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →