Int to Roman

Int to Roman

Integer to Roman

Problem

Roman numerals use seven symbols:

Given an integer num, convert it to a Roman numeral.

The rules are:

• If the value does not start with 4 or 9, pick the biggest symbol that fits. Append it, subtract its value, and repeat with the remainder.
• If the value starts with 4 or 9, use the subtractive form. Only these six forms are used: IV (4), IX (9), XL (40), XC (90), CD (400) and CM (900).
• Only I, X, C and M can repeat, and at most 3 times in a row. V, L and D never repeat. If a symbol is needed 4 times, use the subtractive form.

Examples

Example 1

Input: num = 3749
Output: "MMMDCCXLIX"

• 3000 = MMM
• 700 = DCC
• 40 = XL
• 9 = IX
• 49 is not IL, because we convert each decimal place on its own.

Example 2

Input: num = 58
Output: "LVIII"

• 50 = L
• 8 = VIII

Example 3

Input: num = 1994
Output: "MCMXCIV"

• 1000 = M
• 900 = CM
• 90 = XC
• 4 = IV

Constraints

• 1 <= num <= 3999

Main Idea

This is a greedy problem. At each step, we take the biggest value that fits into the number.

The trick is to include the six subtractive forms in our list of values. Then we do not need special rules for 4 and 9. We keep two arrays in the same order, from biggest to smallest:

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

Steps

• Start at the biggest value (i = 0).
• If num >= values[i], append symbols[i] and subtract values[i] from num.
• Otherwise, move to the next smaller value (i++).
• Stop when num becomes 0.

Why does greedy work? The list has every value that can start a Roman part, including the subtractive ones. So taking the biggest fitting value never breaks the rules. A symbol like C can repeat at most 3 times, because the fourth one would be CD, which comes earlier in the list.

Solution: Greedy

var intToRoman = function (num) {
    const n = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];

    const s = [
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV", "I"
    ];

    let i = 0;
    let str = "";

    while (num > 0) {
        if (num >= n[i]) {
            // this value fits, so use it
            str += s[i];
            num -= n[i];
        } else {
            // too big, so try the next smaller value
            i++;
        }
    }

    return str;
};

How the Code Works

Step 1: Set up the two arrays

• n holds the values from big to small.
• s holds the matching symbols at the same index.

Step 2: Loop until num is 0

• i points to the value we are trying now.
• str is the Roman numeral we are building.

Step 3: Fit or move on

• If num >= n[i], we append s[i] and subtract n[i]. We do not move i, because the same value may fit again (for example, MMM).
• Otherwise, we do i++ to try a smaller value.
• i never goes past the last index. The last value is 1, and num > 0 always fits 1.

Dry Run

Let us take num = 1994.

num is now 0, so the answer is "MCMXCIV".

Alternative: Place-Value Lookup

We can also look up each decimal digit in a table. For every place (thousands, hundreds, tens, ones), we already know the Roman text for digits 0 to 9.

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

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

• It has no loop. We just read four table values and join them.
• For 3749: MMM + DCC + XL + IX = "MMMDCCXLIX".

Complexity

For both solutions, the input is limited to 3999, so the work is fixed.

• Time Complexity: O(1)
  • The greedy loop runs at most a fixed number of times: up to 13 moves of i, plus at most about 15 appended symbols (the longest answer is MMMDCCCLXXXVIII).
  • If we think in general terms, the work grows with the number of output symbols.
• Space Complexity: O(1)
  • The arrays have a fixed size, and the result is at most 15 characters.

Comparison

Summary

• Roman numerals are built from big values to small values, so greedy works.
• We add the six subtractive forms (CM, CD, XC, XL, IX, IV) to the value list. This handles the 4 and 9 rules without extra code.
• If the value fits, we append it and subtract. We stay on the same index so it can repeat.
• If the value does not fit, we move to the next smaller one.
• The place-value lookup is a loop-free alternative that reads one table entry per digit.
• Both solutions run in O(1) time and use O(1) space, because num is at most 3999.