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 )