Integer to Roman — InterviewPrepKit

Solving tips

Fold the six subtractive pairs (CM, CD, XC, XL, IX, IV) into the value table as first-class entries so the loop stays uniform.
Process the descending value/symbol table greedily: use divmod(num, value) to get both the repeat count and remainder in one step.
The table must be strictly descending by value for greedy to be correct; alternatively use per-digit lookup tables since num <= 3999.
Everything is bounded, so this is O(1) time and space.

Problem

Roman numerals use seven symbols: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Numbers are built by writing symbols from largest value to smallest and concatenating them, with six subtractive forms to avoid four-in-a-row: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Given an integer num, convert it to its Roman numeral string.

Examples

num = 3 → "III" — three ones.
num = 58 → "LVIII" — 50 (L) + 5 (V) + 3 (III).
num = 1994 → "MCMXCIV" — 1000 (M) + 900 (CM) + 90 (XC) + 4 (IV).

Constraints

1 <= num <= 3999

Think about it first

Hint 1

Include the six subtractive pairs as if they were their own "symbols" with values 900, 400, 90, 40, 9, 4. Then every number is just a sum of values drawn from a fixed list.

Hint 2

Process the value/symbol pairs from largest to smallest. Greedily take as many copies of the current symbol as fit, subtract, and move on — this is optimal because Roman numerals are constructed exactly this way.

Hint 3

`divmod(num, value)` gives you both the repeat count and the remainder in one step. Alternatively, precompute per-digit tables (thousands, hundreds, tens, ones) and index into them.

TL;DR

Greedily subtract from a descending value→symbol table (including the subtractive pairs) — O(1) time and space (the table and output are bounded).

Approach 1 — Greedy over a value/symbol table

The insight: if you treat the six subtractive forms (CM, CD, XC, XL, IX, IV) as first-class entries in a descending value table, then building the numeral is pure greedy: repeatedly append the largest symbol that still fits and subtract its value. Greedy is optimal here because the Roman system is designed so that each value is written with as many high-value symbols as possible.

class Solution:
    def intToRoman(self, num: int) -> str:
        table = [
            (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"),
        ]
        parts = []
        for value, symbol in table:
            if num == 0:
                break
            count, num = divmod(num, value)
            parts.append(symbol * count)
        return "".join(parts)

Walkthrough with num = 1994:

value, symbol	divmod	append	num left
1000, M	1994 // 1000 = 1, rem 994	`"M"`	994
900, CM	994 // 900 = 1, rem 94	`"CM"`	94
90, XC	94 // 90 = 1, rem 4	`"XC"`	4
4, IV	4 // 4 = 1, rem 0	`"IV"`	0

Joining gives "MCMXCIV". (Entries whose value exceeds the remaining num yield count 0 and contribute nothing.)

Complexity: the table has 13 fixed entries and the output is at most ~15 characters, so this is O(1) time and O(1) space in num.

Approach 2 — Per-digit lookup tables

The insight: since num <= 3999, it has at most four decimal digits, and each digit position maps to a small fixed set of numeral strings. Precompute the ten possibilities for thousands, hundreds, tens, and ones, then index by each digit and concatenate — no loop, no arithmetic beyond extracting digits.

class Solution:
    def intToRoman(self, num: int) -> str:
        thousands = ["", "M", "MM", "MMM"]
        hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return (
            thousands[num // 1000]
            + hundreds[num // 100 % 10]
            + tens[num // 10 % 10]
            + ones[num % 10]
        )

Walkthrough with num = 58: thousands[0] = "", hundreds[0] = "", tens[5] = "L", ones[8] = "VIII" → "LVIII".

Complexity: O(1) time and space — four constant-size table lookups.

Common pitfalls

Omitting the subtractive pairs from the greedy table; without them you’d emit "IIII" instead of "IV".
Ordering the table incorrectly — it must be strictly descending by value for the greedy step to be correct.
In the digit-table version, forgetting the % 10 when extracting the hundreds and tens digits.

Pattern takeaway

When a target notation has a small, fixed alphabet of “denominations,” a greedy largest-first subtraction (like making change with canonical coin systems) produces the encoding directly. Folding the exceptional cases (subtractive pairs) into the denomination list keeps the loop uniform and branch-free.