Integer to Roman: The Greedy Mapping That Always Shows Up in Interviews

Problem Statement

Given an integer num, convert it to a Roman numeral string. Roman numerals are formed from seven base symbols:

Important rule — subtractive notation. Numbers like 4 are not written as IIII, but as IV (5 - 1). Similarly:

Constraints: 1 <= num <= 3999

Examples:

Input:  num = 3749
Output: "MMMDCCXLIX"

Input:  num = 58
Output: "LVIII"

Intuition — Greedy

Roman numerals are always built from the largest symbol that fits. This is not a coincidence — it is inherent to the Roman numeral system.

Take 58: the largest symbol ≤ 58 is L (50). Remainder 8. Largest symbol ≤ 8 is V (5). Remainder 3. Three Is. Result: "LVIII".

Take 3749: start with M (1000) three times → "MMM", remainder 749. Next D (500) → "MMMD", remainder 249. Next C (100) twice → "MMMDCC", remainder 49. Next XL (40) → "MMMDCCXL", remainder 9. Next IX (9) → "MMMDCCXLIX".

The pattern is always the same: pick the largest symbol ≤ remaining value, subtract, repeat.

The Right Mapping

We need all possible symbols — including subtractive cases — sorted from largest to smallest:

mapping := []struct {
    value  int
    symbol string
}{
    {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"},
}

Thirteen symbols. Descending order. Why 13? Because we include the 6 subtractive cases as atomic symbols in the mapping. This makes the algorithm pure greedy — no special logic needed to detect 4 or 9.

Solution — Greedy O(1)

func intToRoman(num int) string {
    mapping := []struct {
        value  int
        symbol string
    }{
        {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"},
    }

    var result strings.Builder
    for _, pair := range mapping {
        for num >= pair.value {
            result.WriteString(pair.symbol)
            num -= pair.value
        }
    }

    return result.String()
}

Visualization

num = 3749

value=1000 (M):  num=3749 → "M",   num=2749 → "M",   num=1749 → "M",   num=749 → stop (749 < 1000)
                  result = ["M","M","M"], num = 749

value=900  (CM): 749 < 900 → skip

value=500  (D):  749 ≥ 500 → "D", num = 249
                  result = ["M","M","M","D"], num = 249

value=400  (CD): 249 < 400 → skip

value=100  (C):  249 ≥ 100 → "C", num = 149 → "C", num = 49 → stop (49 < 100)
                  result = ["M","M","M","D","C","C"], num = 49

value=90   (XC): 49 < 90 → skip

value=50   (L):  49 < 50 → skip

value=40   (XL): 49 ≥ 40 → "XL", num = 9
                  result = ["M","M","M","D","C","C","XL"], num = 9

value=10   (X):  9 < 10 → skip

value=9    (IX): 9 ≥ 9 → "IX", num = 0
                  result = ["M","M","M","D","C","C","XL","IX"], num = 0

Join → "MMMDCCXLIX"

Why Greedy Works

Some problems cannot be solved with a greedy approach (e.g., coin change with certain denominations). But this problem is always greedy-optimal because:

1. Roman symbols form a canonical coin system — each time we take the largest symbol that fits, we will never end up in a situation where a combination of smaller symbols could produce a shorter representation.
2. The 1-3999 constraint guarantees we don't need symbols beyond MMM (3000) or special cases beyond thousands.

Complexity

Since num ≤ 3999, complexity is constant. For the general case (any integer), it remains O(log n) since the number of symbols per digit is bounded.

Alternate Approach — Divide by Place Value

An alternative is processing per digit (thousands/hundreds/tens/ones):

func intToRoman(num int) string {
    thousands := []string{"", "M", "MM", "MMM"}
    hundreds  := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    tens      := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    ones      := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}

    return thousands[num/1000] +
           hundreds[(num%1000)/100] +
           tens[(num%100)/10] +
           ones[num%10]
}

Also O(1) and more explicit, but the greedy version is more flexible if the rules ever change.

Key Takeaway

Sort symbols descending. While the number is large enough for a symbol, append it and subtract. Repeat.

This problem tests whether you can recognize the greedy choice property — that picking the largest symbol that fits will never invalidate the optimal solution. Once you realize that, the implementation is trivial.