💬 Discord
Sign In
NeetCode #914LC-12MediumMath & Geometry
← Back to All Problems

#914 · #12 · Integer to Roman(整数转罗马数字)

📌 Problem Statement & Constraints

Given an integer num, convert it to a Roman numeral. Roman numerals use the symbols I, V, X, L, C, D, M plus the six subtractive pairs IV, IX, XL, XC, CD, CM. Constraints: 1 <= num <= 3999.

💡 Core Algorithmic Approaches

  1. List the symbol values in descending order, including the six subtractive pairs as first-class entries in the table.
  2. Greedily take as many copies of the largest value that fits, then move to the next smaller value.
  3. Because CM, CD, XC, XL, IX and IV are in the table, no special-case branching is needed anywhere.
  4. Concatenating the pieces produced in this order yields the correct numeral.

💻 Benchmark Python3 Implementation

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [
            (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"),
        ]
        res = []
        for v, sym in values:
            if num == 0:
                break
            count, num = divmod(num, v)     # repeat count + remainder
            res.append(sym * count)
        return "".join(res)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): the table is fixed and num <= 3999 bounds the output length.
💾 Space Complexity
O(1): the output is bounded by a small constant number of characters.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the subtractive pairs from the table: 4, 9, 40, 90, 400 and 900 would then render as IIII, VIIII, and so on.
  • Sorting the table ascending: the greedy step requires descending order.
  • Using num % v and forgetting the quotient: divmod returns both the repeat count and the remainder needed for the next iteration.
  • Appending with repeated string concatenation: list accumulation plus a single join is cleaner and avoids quadratic behaviour.