Cover image by Creed Ferguson (Unsplash)
Introduction
This post was inspired by two challenges I solved on LeetCode. One of them was creating a function to convert Roman numerals to integers and the second one was creating a function to do the opposite.
Click on the highlighted headings if you wish to see the problems statements on LeetCode.
Roman numeral to Integer
A string is given and its length goes from 1 to 15; it contains only the characters 'I', 'V', 'X', 'L', 'C', 'D', 'M'
; it's guaranteed that the string is a valid Roman numeral in the range [1, 3999]
. So the task is to convert the given string that represents a Roman numeral to its respective integer. Also consider the following statements:
-
I
can be placed beforeV
(5) andX
(10) to make 4 and 9. -
X
can be placed beforeL
(50) andC
(100) to make 40 and 90. -
C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.
Discussing a solution
The approach I've used to solve this challenge was iterating over the string and executing a condition that meets the subtraction principles described above in the problem statement, in order to return the result corresponding to the final sum.
The condition says: if the current character is greater than the previous character, then subtract the previous character value from the result, otherwise increment the value of the previous character to the result.
For example, if we consider the string s = 'XIV'
, the first character 'X'
whose value is 10
will satisfy the condition, since the previousChar
variable is initialized with 0
, then result
still remains 0
.
The second character 'I'
whose value is 1
won't satisfy the condition once 1
isn't greater than previousChar
which is now 10
. So result
is incremented by 10
and previousChar
is updated to 1
.
Finally, the third character 'V'
whose value is 5
will satisfy the condition because is greater than previousChar
. So from the result
is subtracted 1
and previousChar
is updated to 5.
The code finishes the loop with result = 9
and finally increments the value of previousChar
to the result
. So our final result
becomes 14
.
The solution
Here is an example of a Python solution:
numbersDict = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}
def romanToInt(s):
result = 0
previousChar = 0
for char in s:
if numbersDict[char] > previousChar:
result -= previousChar
else:
result += previousChar
previousChar = numbersDict[char]
result += previousChar
return result
Integer to Roman numeral
An integer in the range 1 <= num <= 3999
is given and the task is to convert it to a Roman numeral.
Discussing a solution
As in the solution of the previous problem, first we create a dictionary
to map the integers and their respective Roman numerals. But unlike the previous challenge, where we only mapped the single character Roman numerals, in this case we also need to map the integers 4 and 9 and their successors up to 1000, which are 40, 90, 400 and 900.
It's also important to mention for this case I've ordered the tuples array in a descending order because it will be relevant for each iteration when executing the necessary checks.
So after that first step, we create a function to make the conversion. The idea is similar to the previous challenge except now, instead of incrementing a value to the counter until we iterate the entire string, we will subtract a value from the given number and concatenate its respective Roman numeral to a string type variable called result
.
Solution
Here is an example of a Python solution:
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')
]
def intToRoman(num):
remaining = num
result = ''
for integerValue, romanNumeral in numbersDict:
while remaining >= integerValue:
result += romanNumeral
remaining -= integerValue
return result
Then the same solution in JavaScript:
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;
};
Considerations
For more details on the solutions such as time and space complexity, check out my contributions to LeetCode The Hard Way:
Top comments (0)