Given an integer num between 1 and 3999, return its Roman numeral. Use the standard symbols I, V, X, L, C, D, M and the six subtractive forms IV, IX, XL, XC, CD, CM, always choosing the form that uses the largest possible symbols first (so 4 is IV, not IIII).
- 1 <= num <= 3999
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Handling each digit with special cases for 4 and 9 works but gets messy. The cleaner view is greedy change-making: list the 13 values including the subtractive pairs, sorted from big to small. Repeatedly take the largest value that fits into what is left and append its symbol. This always gives the standard numeral because the subtractive pairs are exactly the cases where the normal symbols would repeat four times.
Algorithm
- Make parallel lists
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]and their symbols. - For each value from largest to smallest, while
num >= value, append the symbol and subtract the value. - Return the built string.
O(1), the output has at most 15 symbolsSpace: O(1)class Solution: def intToRoman(self, num: int) -> str: values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] out = [] for v, sym in zip(values, symbols): while num >= v: # take the largest symbol that fits out.append(sym) num -= v return "".join(out)