12. Integer to Roman

Integer to Roman

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numerals, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written from largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

 

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 

Constraints:

• 1 <= num <= 3999

For all of the below solutions, we’re required to create an array of potential numerals. But what’s interesting is that one requires only the traditional numerals (I, V, X, L, C, D & M), whilst another also requires doubles (CM, CD, XC, etc.), and the last requires all combinations (M, MM, MMM, C, CC, CCC, CD, D, DC, DCC, DCCC, CM, etc.).

There is very little difference in terms of the performance for all 3 (at least using JavaScript).

Approach 1) If statements (recursive)

Ugly at first, I know, but this solution is borderline elegant in its readability. 

We take a number, match it to and return the highest available roman numeral, and then append the result of calling the whole process again on what remains (AKA we run the function recursively until we’re done):

Lets Code It

const numerals = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };

var intToRoman = function (num) {
    if (num < 1) return '';
    if (num >= 1000) return 'M' + intToRoman(num - 1000);
    if (num >= 900) return 'CM' + intToRoman(num - 900);
    if (num >= 500) return 'D' + intToRoman(num - 500);
    if (num >= 400) return 'CD' + intToRoman(num - 400);
    if (num >= 100) return 'C' + intToRoman(num - 100);
    if (num >= 90) return 'XC' + intToRoman(num - 90);
    if (num >= 50) return 'L' + intToRoman(num - 50);
    if (num >= 40) return 'XL' + intToRoman(num - 40);
    if (num >= 10) return 'X' + intToRoman(num - 10);
    if (num >= 9) return 'IX' + intToRoman(num - 9);
    if (num >= 5) return 'V' + intToRoman(num - 5);
    if (num >= 4) return 'IV' + intToRoman(num - 4);
    if (num >= 1) return 'I' + intToRoman(num - 1);
    return num;
};

Approach 2): Looping

This suggestion came from LeetCode user kkang, and uses separate arrays to track numerals and their respective values.

What this solution does is run until the input number has reached 0. For each iteration, it loops through the available numeral values, finds the biggest one applicable to the outstanding number, stores the corresponding numeral into a global string, and then removes the numeral’s value from the outstanding number. It’s actually pretty similar to solution #1, but without the if statements and recursion:

Lets Code It

var intToRoman = function (num) {
    const list = ['M','CM','D','CD','C','XC','L','XL','X','IX','V','IV','I'];
    const valueList = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let result = '';

    // Run until we have converted the full number
    while (num !== 0) {
        // Loop though the available numerals
        for (let i = 0; i < list.length; i++) {
            // Check if the outstanding number is greater than the current numeral
            if (num >= valueList[i]) {
                // If so, add this numeral to the result and subtract its value from the outstanding number
                result += list[i];
                num -= valueList[i];
                break;
            }
        }
    }
    return result;
};

Solution #3: Math

This incredibly concise solution comes from LeetCode user fabrizio3, and uses just a little bit of math to get the job done.

The way it works is that it first initializes every combination of letters for each level of the numeral (1, 10, 100, 1,000) in an array that starts with an empty value. Then, it calculates which array element to apply based on the modulo and/or division of the overall number by the relevant level (the exact path differs by level). The inclusion of the empty first element handles cases where the number is lower than that level (such as 500 is lower than the 1,000 level)

I’d say it’s a little less readable than the others, but it’s certainly elegant:

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function (num) {
    let M = ["", "M", "MM", "MMM"];
    let C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
    let X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
    let I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
    return M[parseInt(num/1000)] + C[parseInt((num%1000)/100)] + X[parseInt((num%100)/10)] + I[parseInt(num%10)];
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem #12. Integer to Roman

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!