{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Integer to Roman – Solution & Complexity

Interview solutions
/
Integer to Roman

Solution Walkthrough

  1. Step 1: Model the symbol table

    • List the thirteen value/symbol pairs in descending order of value, with the six subtractive forms (CM, CD, XC, XL, IX, IV) interleaved at their exact values.
    • Including the subtractive pairs directly in the table is what lets a plain greedy loop emit canonical numerals without special cases.

  2. Step 2: Greedily subtract

    • Walk the table from largest value to smallest.
    • While the remaining number is at least the current value, append that symbol and subtract the value.
    • Move to the next pair when the current one no longer fits.

  3. Step 3: Why greedy is safe here

    • Each ordinary symbol repeats at most three times before the next subtractive form takes over (e.g. III then IV), so the table encodes the "no four-in-a-row" rule implicitly.
    • Taking the largest usable value can never force an invalid or longer representation, because the smaller values can always cover whatever remainder is left.

  4. Step 4: Optimal greedy solution

    • Build the result string in one descending pass.
    • Time is O(1) because the table size is fixed and the number is bounded by 3999; space is O(1) beyond the output.
    def int_to_roman(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"]
    result = []
    for value, symbol in zip(values, symbols):
        while num >= value:
            result.append(symbol)
            num -= value
    return "".join(result)

  5. Step 5: Common mistakes

    • Forgetting the subtractive pairs and emitting IIII instead of IV.
    • Using if instead of while, which stops after a single M when the number needs several.
    • Listing the table out of order so a larger symbol is reachable after a smaller one was already applied.

FAQ

See also

Practice Integer to Roman online (run code in the browser)Excel Sheet Column Number solution (easy)FizzBuzz solution (easy)Roman to Integer solution (easy)Add Two Numbers solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?