Roman Numeral To Integer

Easy
0/40
Average time to solve is 15m
profile
Contributed by
74 upvotes
Asked in companies
UberFacebookBarclays

Problem statement

You are given a string 's' that represents a Roman number. Convert the Roman number to an integer and return it.


Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.


Table of values: 
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example: 
3 is written as III in Roman numeral, just three ones added together. 13 is written as XIII, which is simply X + III. The number 25 is written as XXV, which is XX + V
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains a string ‘roman’ representing the number's roman number representation.
Output Format 
The only line contains a single integer denoting the integer value of the given roman number.
Note: 
Do not print anything, just return an integer denoting the equivalent integer of the given roman number

It is guaranteed that the string input is one of the characters of I, V, X, L, C, D, M.

It is guaranteed that the integer value of the given roman number will not exceed 3999.
Sample Input 1:
XII
Sample Output 1:
12
Explanation For Sample Input 1 :
We know that ‘X’ is 10, and we have 2 ‘I’ after it. Therefore the number is 12
Sample Input 2:
XC
Sample Output 2:
90
Constraints:
1 <= roman.length <= 15

Time limit: 1 second
Follow Up:
Can you solve this in O(N) time?
Hint

Can you deduce a recursive relation using rules of roman numbers?

Approaches (2)
Recursive Approach

The key idea is to follow the rules of roman numbers which are as follows:

 

  • The roman digits I, X and C are repeated up to three times in succession to form the numbers.
  • When a digit of lower value is written to the right or after a digit of higher value, the values of all the digits are added.
  • When a digit of lower value is written to the left or before a digit of higher value, then the value of the lower digit is subtracted from the value of the digit of higher value.
  • If we have to write the numbers beyond 10 we should write the number 10 or groups of number 10 and then number 1 or 5 as the case may be. Then these numbers are used to change to the corresponding Roman numerals.

 

Keeping the above example in mind, we can write the following recursive solution:

 

  • We take a recursive approach to solve the problem.
  • We make a hash map ‘conv’ which stores integer values of special roman numbers.
  • Then, we take the first 2 characters and check if they are in the map, if yes we add their value and recursively call the rest of the string.
  • If the first 2 characters are not there in the map, we add the value of 1 character and recursively call the rest of the string.
  • The base case will be once we have a string of size 1 or an empty string. In that case, we return 0.
Time Complexity

O(N), Where ‘N’ denotes the length of the string.

 

Since we traverse the string once to find the integer value. Hence the overall time complexity is O(N).

Space Complexity

O(N), Where ‘N’ denotes the length of the string.

 

It is because the recursive stack uses space of order of ‘N’. Hence the overall space complexity is O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Roman Numeral To Integer
Full screen
Console