012.md

12. Integer to Roman

Difficulty: 🟡 Medium

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 one's 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.

Examples:

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

Solutions

O(1) solution

Python3

def intToRoman(self, num: int) -> str:
        mapping = {
            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”
        }
        result = []
        for key in sorted(mapping.keys(), reverse=True):
            if key <= num:
                result.append(mapping[key] * (num // key))
                num %= key
        return “”.join(result)

The given solution solves the problem by performing the following steps:

1. Create a mapping that maps each numeral value to its corresponding Roman numeral representation. The mapping contains the base values and the special cases where subtraction is used.
2. Initialize an empty list result to store the Roman numeral representation of the number.
3. Iterate through the keys of the mapping in descending order.
   • Check if the current key is less than or equal to num.
     • If true, append the Roman numeral representation of the current key to result repeated num // key times.
     • Update num by taking the modulus of num with the current key.
4. Finally, join the elements of result into a single string and return it as the Roman numeral representation of the given number.

Complexity Analysis

The time complexity of this algorithm is O(1) because the maximum number of iterations in the loop is constant. The loop iterates through the keys of the mapping, which is a fixed-size set of values.

The space complexity of the algorithm is also O(1) because the size of the output string is bounded by the given constraints.

Summary

The given solution converts an integer num into its Roman numeral representation. It uses a mapping of base values and special cases to construct the Roman numeral representation. The algorithm has a time complexity of O(1) and a space complexity of O(1), making it efficient for the given constraints.

NB: If you want to get community points please suggest solutions in other languages as merge requests.