Problem Statement:
You are given a roman numeral, you need to convert into it’s corresponding decimal value.
Example
Input: IX
Output: 9
Solution
The solution is very simple.
We need to know what each roman numeral maps to decimal.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
Now for example if our string is “VII” then we just add the numbers “5 + 1 + 1 = 7”.
But we need to take care when the number on the right is greater than left. Example “IV”.
In this case we need to find the difference “1 – 5 = 4”.
Based on that we will arrive at the solution.
In the solution, we start by working the string from the back to front.
The time complexity is O(n)
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int roman_to_int(string s)
{
unordered_map<char, int> T = { { 'I' , 1 },
{ 'V' , 5 },
{ 'X' , 10 },
{ 'L' , 50 },
{ 'C' , 100 },
{ 'D' , 500 },
{ 'M' , 1000 } };
int sum = T[s.back()];
for (int i = s.length() - 2; i >= 0; --i)
{
if (T[s[i]] < T[s[i + 1]])
{
sum -= T[s[i]];
}
else
{
sum += T[s[i]];
}
}
return sum;
}
int main()
{
string str = "IV";
cout << "Roman to Integer is "
<< roman_to_int(str) << endl;
return 0;
}
Output:
Roman to Integer is 4