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