MediumHash TableMathStringUpdated Sep 2026

12. Integer to Roman

Asked at Meta, Salesforce

Difficulty

Medium

Time

O(1)

Space

O(1)

Pattern

Hash Table

Companies

2

Problem

You are given a positive integer num. Convert it into its Roman numeral string.

Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. Normally you write the biggest symbol that fits, then repeat with what is left. But when a digit is 4 or 9, you use a subtractive form instead: a smaller symbol placed before a bigger one means subtraction. Only these six subtractive forms exist: IV (4), IX (9), XL (40), XC (90), CD (400), CM (900).

The tricky part is that subtraction is decided per decimal place, not on the whole number. So 49 is XLIX (40 + 9), not IL. Also, the symbols V, L and D may never be repeated, and I, X, C, M may appear at most three times in a row.

Return the Roman numeral as a string.

Split the number by decimal place

3749300070040940 and 9 are the digits that need a subtractive formromanMMMDCCXLIXXL = 50 − 10 and IX = 10 − 1, so the small symbol goesfirst
Each digit is converted on its own, then the pieces are joined in order from thousands down to ones.

Constraints

  • ●1 <= num <= 3999

Examples

Example 1
Inputnum = 3749
Output"MMMDCCXLIX"
WhySplit by place: 3000 = MMM, 700 = DCC, 40 = XL, 9 = IX. Joining them gives MMMDCCXLIX.
Example 2
Inputnum = 58
Output"LVIII"
Why50 = L and 8 = VIII, so the answer is L + VIII = LVIII.
Example 3
Inputnum = 1994
Output"MCMXCIV"
Why1000 = M, 900 = CM, 90 = XC, 4 = IV. Put together: MCMXCIV.

Asked At

2 companies
CompanyDifficulty
MetaMediumView all Meta questions →
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Brute force: repeatedly subtract the largest possible Roman value and append its symbol. Without a map, you would need many if/else branches. This works but is messy and hard to maintain.

2

Key insight: create a sorted list of (value, symbol) pairs from largest to smallest: [(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")]. Greedily pick the largest value that fits.

3

Why include subtractive pairs: 4 is "IV" not "IIII", 9 is "IX" not "VIIII". Include these as explicit entries in your map so the greedy algorithm picks them directly.

4

Complexity: O(1) because the loop runs at most 15 times (for 3999, the max input). Space is O(1) for the output string.

Optimal Approach

Create a sorted list of (value, symbol) pairs in descending order, including subtractive forms like 900/"CM" and 4/"IV". Iterate through the list. For each pair, while num >= value, append the symbol to the result and subtract the value from num. Continue until num reaches 0.

Walkthrough with num = 58:

  • 58 >= 50 ("L"): append "L", num = 8
  • 8 >= 5 ("V"): append "V", num = 3
  • 3 >= 1 ("I"): append "I", num = 2
  • 2 >= 1 ("I"): append "I", num = 1
  • 1 >= 1 ("I"): append "I", num = 0
  • Result: "LVIII"

Time: O(1) — fixed 13 entries, at most 15 iterations. Space: O(1) — output length is bounded.

Greedy with a value table

list (1000,M) ... (1,I)while num >= value: append symbol, num -= vastop when num = 0The table already contains the six subtractive pairs,so the loop never needs special cases.num = 58588321058 → take L (50) → take V (5) → take I three times → 0result = "L" + "V" + "I" + "I" + "I"answer = "LVIII"
Walk the table from the biggest value down. Take a value as many times as it fits, then move on.
ComplexityTime O(1)Space O(1)The value list has 13 fixed entries and the loop runs a bounded number of times, so both time and space are constant.

What Trips People Up in Real Interviews

1

Forgetting the subtractive forms like 4 ("IV") and 9 ("IX"). Without them in the map, you get "IIII" instead of "IV", which is wrong.

2

Not sorting the value map in descending order. The greedy approach requires processing largest values first. If you iterate from smallest, you get the wrong result.

3

Assuming the input can be 0 or negative. The problem constraints say 1 <= num <= 3999, but clarify with the interviewer before coding.

4

Building the string by prepending instead of appending. Each greedy step gives the largest remaining value, so append is correct. Prepending would reverse the result.

5

Hardcoding each case individually instead of using the map-based loop. Interviewers want to see a clean, generalizable pattern, not a 200-line if/else chain.

Solution Code

O(1) time
def intToRoman(num):
    val_sym = [
        (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')
    ]
    result = ''
    for val, sym in val_sym:
        while num >= val:
            result += sym
            num -= val
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Integer to Roman problem?

Convert an integer to a Roman numeral. Roman numerals are represented by seven symbols: I, V, X, L, C, D, M with fixed values. This problem tests your ability to decompose a number greedily using a value map.

How do you solve Integer to Roman?

The optimal approach runs in O(1) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Integer to Roman?

Integer to Roman is asked at Meta, Salesforce. It is a medium difficulty problem.

What are common mistakes on Integer to Roman?
  • Forgetting the subtractive forms like 4 ("IV") and 9 ("IX"). Without them in the map, you get "IIII" instead of "IV", which is wrong.
  • Not sorting the value map in descending order. The greedy approach requires processing largest values first. If you iterate from smallest, you get the wrong result.
  • Assuming the input can be 0 or negative. The problem constraints say 1 <= num <= 3999, but clarify with the interviewer before coding.
  • Building the string by prepending instead of appending. Each greedy step gives the largest remaining value, so append is correct. Prepending would reverse the result.
  • Hardcoding each case individually instead of using the map-based loop. Interviewers want to see a clean, generalizable pattern, not a 200-line if/else chain.