Convert Roman Numerals to Integers
Difficulty: Medium
Asked in: Amazon, Microsoft, Facebook
Understanding the Problem
Problem Description: Given a Roman numeral as input, your task is to find its corresponding integer value and output it. Roman Numerals are represented by combinations of letters from the Latin alphabet.
Example:
Input: XII
Output:12
Input: MIV
Output:1004
Possible follow up question:
- What is the range of the input Roman numerals?( Ans: Consider 1–3999 is the required range for this problem )
Solution
Solution idea
Before understanding the Solution let’s first analyze Roman numerals. The following Latin alphabets are used to write Roman numerals till 3999→
ALPHABET VALUE
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Note: Please look at the following Roman representations
IV is for 4
IX is for 9
XL is for 40
XC is for 90
Similarly, Can you guess what CD and CM represents? (Yes! You are right 400 and 900 respectively)
A roman numeral is generally written in decreasing order that is the symbol for 500 will come before the symbol for 100, the symbol for 1000 will come before the symbol for 500. However, there are certain situations when this descending order is violated. In order to avoid four symbols to represent an integers like in the following cases: →IIII for writing 4, CCCC for writing 400, etc. We follow a different notation based on subtraction known as “ Subtractive Notation ”.
Subtractive Notation: Subtractive notation is used to replace the four or five character representation of the Roman numeral with the corresponding shorthand representation. In this, a symbol of lower value is placed before the symbol of higher value in order to represent numerals like four, nine, four hundred, etc.Example: IV is for 4, IX is for 9, CD is for 400, etc.Note: The symbol I(1) is never used for higher value in this notation.
Solution Steps
The following are the steps used to convert Roman numerals into corresponding integers:
- Whatever Roman numeral is given , We will process on each symbol of the given string.
- Every symbol has its corresponding value, so we will find the value of each symbol in the string.
- Starting from the index first (that is 0), we will follow either addition or subtraction to get the required integer based on the following condition:
- If the symbol at the taken index is greater than the next index symbol(in terms of value like V > I), we will simply add the values of both the indices in the total(that is the variable for integer value), this is additive notation.
- If the symbol at the taken index is smaller than the next index symbol(in terms of value), we will subtract its value from the greater symbol value and add the result to the running total.
Pseudo-Code
int getValue(char symbol)
{
if(symbol=='I' || symbol=='i')
return 1
if(symbol=='V' || symbol=='v')
return 5
if(symbol=='X' || symbol=='x')
return 10
if(symbol=='L' || symbol=='l')
return 50
if(symbol=='C' || symbol=='c')
return 100
if(symbol=='D' || symbol=='d')
return 500
if(symbol=='M' || symbol=='m')
return 1000
return -1
}
int romanToInteger(string Roman, int size)
{
int resultInt = 0
for(i = 0 to size - 1, i = i+1)
{
int val = getValue(Roman[i])
if(i < size - 2)
{
int valNext = getValue(Roman[i+1])
if(val >= valNext)
resultInt = resultInt + val
else
{
int afterSub = valNext - val
resultInt = resultInt + afterSub
i = i + 1
}
}
else
resultInt = resultInt + val
}
return resultInt
}
Complexity Analysis
Time Complexity = O(L), where L is the size of the given Roman string.
Space Complexity = O(1)
Critical ideas to think!
- Can you think how to convert Integer to Roman numeral?( Hint : Try converting using 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 as the base )
Suggested Problems to Solve
- Convert Integer to corresponding Roman numeral.
- Convert Integer to Binary.
- Exponential notation of a decimal number.
- 9’s complement of a decimal number.
- Decimal to binary conversion using recursion.
Happy Coding! Enjoy Algorithms!!