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.
Example 1:
Input: num = 3 Output: "III"
Example 2:
Input: num = 4 Output: "IV"
Example 3:
Input: num = 9 Output: "IX"
Example 4:
Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.
Example 5:
Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= num <= 3999
The description was taken from https://leetcode.com/problems/integer-to-roman/.
#O(1) Time, O(1) Space
class Solution:
def intToRoman(self, num: int) -> str:
output = []
conversion = { 1:"I",
4:"IV",
5:"V",
9:"IX",
10:"X",
40:"XL",
50:"L",
90:"XC",
100:"C",
400:"CD",
500:"D",
900:"CM",
1000:"M"
}
for key, val in reversed(conversion.items()):
if not num:
break
if key <= num:
frequency = num//key
output.append(val*frequency)
num %= key
return "".join(output)Whenever we are translating one value to another, whether it be an order of words or numbers, it may be a good idea to map the translations for easy access.
From there, we can solve this problem with a somewhat greedy approach, an approach where we prioritize greater Roman numerals over lesser ones within this ordered list.
We can traverse the roman to integer mapping moving from the greatest values first to get the first number less than or equal to the current number. From there, we can calculate the frequency of the Roman numeral by seeing how many times it divides evenly into the current number. After that, we can decrement the current number to what was leftover from the previous calculation and continue this process until the current number becomes zero.
No matter what, we will make a total of iterations equal to the length of the conversion dictionary we create which will be a constant length, so this will result in a constant time and space result.
Let's start by initializing our output and conversion table.
output = []
conversion = { 1:"I",
4:"IV",
5:"V",
9:"IX",
10:"X",
40:"XL",
50:"L",
90:"XC",
100:"C",
400:"CD",
500:"D",
900:"CM",
1000:"M"
}
Next, we will traverse this chart from the greatest values to the smallest.
for key, val in reversed(conversion.items()):
If the current number is zero, we are done.
if not num:
break
Otherwise, we will stop at the first roman numeral number that is less than or equal to the current number.
if key <= num:
We'll calculate the frequency of the Roman numeral that we need by seeing how many times the value in our table divides evenly into the current number.
For example, if we were at the last iteration and had the number three remaining, we would see that three divides evenly by one three times so we would have "III", and could append that to the output.
frequency = num//key
output.append(val*frequency)
To find what we have leftover, we can apply the modulo operator to the previous calculation to get the remaining value and that is what the current number will be decremented to.
num %= key
Once we have our array of Roman numeral symbols, we will join the characters together to form a number string and return it.
return "".join(output)