How to Convert Roman Numerals to Integer
In this post, I will be solving one of the interesting and easy algorithmic questions that appeared in the February 2021 Leetcode Monthly challenge.
PROBLEM STATEMENT
Given the following Roman symbols and their integer representations, write an algorithm to convert Roman Numerals to Integer;
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Few Explanatory Points
Roman numerals are represented by the 7 symbols in the above table and are usually written largest to smallest from left to right. 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
.
However, the numeral for 4 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 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.
Examples
II → 1 + 1 = 2
XII → 10 + 1 + 1 = 12
III → 1 + 1 + 1 = 3
LVIII → 50 + 5 + 1 + 1 + 1
IV → 5 -1 = 4
IX → 10 -1 = 9
XL → 50 -10 = 40
XC → 100 -10 = 90
Looking at the few examples above, you’ll observe the patterns between the Roman numerals and integers. The conversion steps are explained below;
1. Store the Base Roman symbols in a hash map as keys and their integers as hash map values
2. Initialize a “sum” variable to zero and iterate the given Roman string to be converted character-wise starting from the right-most character.
3. For each character in the given string, fetch its integer value from the hash map. If the fetched value of the current roman character is smaller than the integer value of the previous roman character (in front of it), subtract the fetched value from the “sum”, else add it to the sum.
4. Return the “sum” when you get to the left-most character of the given string.
Below is the Java code implementation of the conversion steps.
ANALYSIS
Time complexity: O(N) where N is the length of the given string.
Auxiliary Space: O(1) — there are only 7 symbols in the map which is not affected by the input size.
Thanks for reading! :-)