12. Integer to Roman - Explanation

Description

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

You are given an integer, convert it to a Roman numeral.

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:
3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 1994

Output: "MCMXCIV"

Explanation:
1000 = M
900 = CM
90 = XC
4 = IV

Constraints:

1 <= num <= 3999

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Roman Numeral System - Understanding symbols (I, V, X, L, C, D, M) and subtractive notation (IV, IX, etc.)
Greedy Algorithm - Processing values from largest to smallest to build optimal solutions
Modular Arithmetic - Using division and modulo to extract digits from numbers

1. Math - I

Intuition

Roman numerals are built by combining symbols that represent specific values. The key insight is to process values from largest to smallest, repeatedly subtracting the largest possible value and appending its symbol. We include the subtractive combinations (like IV for 4, IX for 9) in our value list to handle them naturally.

Algorithm

Create a list of symbol-value pairs in ascending order, including subtractive forms (IV, IX, XL, XC, CD, CM).
Iterate through the list from largest to smallest value.
For each pair, divide the remaining number by the value to get the count.
Append the symbol count times to the result and update the number using modulo.
Return the resulting Roman numeral string.

class Solution:
    def intToRoman(self, num: int) -> str:
        symList = [
            ["I", 1], ["IV", 4], ["V", 5], ["IX", 9],
            ["X", 10], ["XL", 40], ["L", 50], ["XC", 90],
            ["C", 100], ["CD", 400], ["D", 500], ["CM", 900],
            ["M", 1000]
        ]

        res = ""
        for sym, val in reversed(symList):
            count = num // val
            if count:
                res += sym * count
                num %= val

        return res

public class Solution {
    public String intToRoman(int num) {
        String[][] symList = {
            {"I", "1"}, {"IV", "4"}, {"V", "5"}, {"IX", "9"},
            {"X", "10"}, {"XL", "40"}, {"L", "50"}, {"XC", "90"},
            {"C", "100"}, {"CD", "400"}, {"D", "500"}, {"CM", "900"},
            {"M", "1000"}
        };

        StringBuilder res = new StringBuilder();
        for (int i = symList.length - 1; i >= 0; i--) {
            String sym = symList[i][0];
            int val = Integer.parseInt(symList[i][1]);
            int count = num / val;
            if (count > 0) {
                res.append(sym.repeat(count));
                num %= val;
            }
        }

        return res.toString();
    }
}

class Solution {
    /**
     * @param {number} num
     * @return {string}
     */
    intToRoman(num) {
        const symList = [
            ['I', 1],
            ['IV', 4],
            ['V', 5],
            ['IX', 9],
            ['X', 10],
            ['XL', 40],
            ['L', 50],
            ['XC', 90],
            ['C', 100],
            ['CD', 400],
            ['D', 500],
            ['CM', 900],
            ['M', 1000],
        ];

        let res = '';
        for (let i = symList.length - 1; i >= 0; i--) {
            const [sym, val] = symList[i];
            let count = Math.floor(num / val);
            if (count > 0) {
                res += sym.repeat(count);
                num %= val;
            }
        }

        return res;
    }
}

public class Solution {
    public string IntToRoman(int num) {
        string[][] symList = new string[][] {
            new[] {"I", "1"},   new[] {"IV", "4"},
            new[] {"V", "5"},   new[] {"IX", "9"},
            new[] {"X", "10"},  new[] {"XL", "40"},
            new[] {"L", "50"},  new[] {"XC", "90"},
            new[] {"C", "100"}, new[] {"CD", "400"},
            new[] {"D", "500"}, new[] {"CM", "900"},
            new[] {"M", "1000"}
        };

        var res = new StringBuilder();
        for (int i = symList.Length - 1; i >= 0; i--) {
            string sym = symList[i][0];
            int val = int.Parse(symList[i][1]);
            int count = num / val;
            for (int k = 0; k < count; k++) {
                res.Append(sym);
            }
            num %= val;
        }

        return res.ToString();
    }
}

class Solution {
    fun intToRoman(num: Int): String {
        val symList = listOf(
            "I" to 1, "IV" to 4, "V" to 5, "IX" to 9,
            "X" to 10, "XL" to 40, "L" to 50, "XC" to 90,
            "C" to 100, "CD" to 400, "D" to 500, "CM" to 900,
            "M" to 1000
        )

        var n = num
        val res = StringBuilder()
        for (i in symList.indices.reversed()) {
            val (sym, v) = symList[i]
            val count = n / v
            repeat(count) {
                res.append(sym)
            }
            n %= v
        }

        return res.toString()
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Math - II

Intuition

Since the input is constrained to 1-3999, we can precompute all possible Roman representations for each digit place (ones, tens, hundreds, thousands). Then we simply look up each digit and concatenate the results. This trades space for simplicity and speed.

Algorithm

Create four arrays containing Roman representations for:
- Thousands: "", "M", "MM", "MMM"
- Hundreds: "", "C", "CC", ... "CM"
- Tens: "", "X", "XX", ... "XC"
- Ones: "", "I", "II", ... "IX"
Extract each digit using division and modulo.
Look up the corresponding string from each array.
Concatenate and return the result.

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 % 1000) // 100] +
            tens[(num % 100) // 10] +
            ones[num % 10]
        )

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

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

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

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

class Solution {
    /**
     * @param {number} num
     * @return {string}
     */
    intToRoman(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]
        );
    }
}

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

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

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]
}

class Solution {
    fun intToRoman(num: Int): String {
        val thousands = arrayOf("", "M", "MM", "MMM")
        val hundreds = arrayOf("", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM")
        val tens = arrayOf("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
        val ones = arrayOf("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")

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

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

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

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Missing Subtractive Combinations

Roman numerals use subtractive notation for 4, 9, 40, 90, 400, and 900 (IV, IX, XL, XC, CD, CM). A common mistake is only including the basic symbols (I, V, X, L, C, D, M) and trying to handle subtractive cases with complex conditional logic. The cleanest solution includes all 13 symbol-value pairs in your lookup table from the start.

Processing Values in Wrong Order

When building the Roman numeral string, you must process values from largest to smallest. Starting with smaller values or processing in random order will produce incorrect results. For example, processing 1994 by handling ones before thousands would give an invalid representation.

Incorrect Division and Modulo Logic

When computing how many times a symbol should appear, some implementations confuse the division and modulo operations. You need integer division to get the count of symbols, then modulo to get the remaining value. Mixing these up or forgetting to update the remaining number after each step leads to wrong outputs or infinite loops.