12. Integer to Roman
Roman numerals spell numbers with seven letters: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. A numeral lists symbols from largest value to smallest and their values add up — with one twist. A symbol is never repeated four times in a row; instead, six subtractive pairs exist, where a smaller symbol written directly before a larger one is subtracted from it: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900.
You receive an integer num with 1 <= num <= 3999. Return the Roman numeral that represents it, as a string.
Example 1:
Input: num = 3749
Output: "MMMDCCXLIX"
Explanation: 3000 = MMM, 700 = DCC (500 + 100 + 100), 40 = XL (50 − 10), 9 = IX (10 − 1).
Example 2:
Input: num = 58
Output: "LVIII"
Explanation: 50 = L, 8 = VIII (5 + 1 + 1 + 1). No subtractive pair is needed.
Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation: 1000 = M, 900 = CM, 90 = XC, 4 = IV — three subtractive pairs in one numeral.
Constraints:
- 1 ≤ num ≤ 3999
Hints:
Work greedily from the largest value downward: peel off as many 1000s as fit, then 900, then 500, and so on. Each step appends a fixed symbol.
Add the six subtractive pairs to your value table as if they were ordinary two-letter symbols — the table becomes 13 entries (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1) and the greedy loop needs no special cases.
Alternative with zero arithmetic: each decimal digit maps independently. Precompute the spellings of 0–9 for the ones, tens, hundreds, and thousands places, then concatenate four lookups.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: num = 3749
Expected output: "MMMDCCXLIX"