Integer to Roman
Asked at Meta, Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
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.
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.
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.
Visual walkthrough for num = 3994:
Map: [(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")]
- 3994 >= 1000: "M", remainder 2994
- 2994 >= 1000: "M", remainder 1994
- 1994 >= 1000: "M", remainder 994
- 994 >= 900: "CM", remainder 94
- 94 >= 90: "XC", remainder 4
- 4 >= 4: "IV", remainder 0
Result: "MMMCMXCIV"
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.