0012 - Integer to Roman (Medium)

Problem Link

https://leetcode.com/problems/integer-to-roman/

Problem Statement

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 numeral, 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 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

Approach 1: Iterating over a list

The solution used was iterating over a tuples list created to map the integers and their respective Roman numerals. So when iterating over the list, while the $remaining$ value is greater than or equal to the first tuple element (which is the integer value), append the corresponding character(s) (the second tuple element) to $result$ and subtract the value from $remaining$.

For example, if we consider the given integer $num = 17$, after starting the iteration over the list, the algorithm checks if the integer $17$ is greater than or equal to the first integer value from the first list element, which is $1000$. Since it's not, the code in the while loop is not executed and the next iteration starts checking if $17$ is greater than or equal to $900$ and so on until the iteration checks if $17$ is greater than or equal to $10$. In this iteration the code in the while loop is executed so that the $result$ variable is concatenated with the respective Roman numeral which is $'X'$ and $remaining$ becomes $7$. For the next iteration, $7$ is not greater than or equal to $9$ but on the next one, when it's greater than $5$, $result$ becomes $'XV'$ and $remaining$ becomes $2$. So keeping that logic, after the final iteration $result$ will be $'XVII'$.

Time Complexity: $O(1)$

The time complexity for this solution is $O(1)$ as the algorithm execution time is independent of the size of the input.

Space Complexity: $O(1)$

The space complexity for this solution is also $O(1)$.

Python

Written by @jessicaribeiroalves

numbersDict = [
    (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')
]

class Solution(object):
    def intToRoman(self, num):
        remaining = num
        result = ''
        for integerValue, romanNumeral in numbersDict:
            while remaining >= integerValue:
                result += romanNumeral
                remaining -= integerValue
        return result

JavaScript

Written by @jessicaribeiroalves

const numbersDict = [
    [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']
];

const intToRoman = (num) => {
    let remaining = num;
    let result = '';

    for (let [integerValue, romanNumeral] of numbersDict) {
        while (remaining >= integerValue) {
            result += romanNumeral;
            remaining -= integerValue;
        }
    }
    return result;
};

C++

Written by @radojicic23

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> numbers = {
            {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"} 
        };
        string ans = "";
        while (num > 0) {
            for (auto [integer, roman] : numbers) {
                if (num >= integer) {
                    ans += roman;
                    num -= integer;
                    break;
                }
            }
        }
        return ans;
    }
};