Leetcode 13. How to Convert a Given Roman Numeral to its Equivalent Integer Value

Convert Roman numerals to integers using subtraction and addition efficiently.

Problem statement

Roman numerals utilize seven symbols: I, V, X, L, C, D, and M to represent numbers.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is denoted as II, which is essentially two ones added together. Similarly, 12 is represented as XII, indicating X + II. The number 27 is written as XXVII, which stands for XX + V + II.

Roman numerals are generally written from the largest value to the smallest value, moving from left to right. However, there are exceptions to this pattern. For instance, the numeral for 4 is IV instead of IIII, where I is placed before V to subtract 1 from 5. Similarly, 9 is IX, representing the subtraction of 1 from 10. There are six such subtraction instances:

• I before V (5) or X (10) forms 4 and 9.
• X before L (50) or C (100) forms 40 and 90.
• C before D (500) or M (1000) forms 400 and 900.

Your task is to convert a given Roman numeral into its equivalent integer value.

Example 1

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints

• 1 <= s.length <= 15.
• s contains only the characters 'I', 'V', 'X', 'L', 'C', 'D', 'M'.
• It is guaranteed that s is a valid Roman numeral in the range [1, 3999].

Solution: Mapping and summing the values

To treat the subtraction cases easier you can iterate the string s backward.

Code

#include <iostream>
#include <unordered_map>
using namespace std;
const unordered_map<char, int> value = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000}
};
int romanToInt(string s) {
    int i = s.length() - 1;
    int result = value.at(s[i--]);
    while (i >= 0) {
        if (value.at(s[i]) < value.at(s[i+1])) {
            result -= value.at(s[i--]); 
        } else {
            result += value.at(s[i--]);
        }
    }
    return result;
}
int main() {
    cout << romanToInt("III") << endl;
    cout << romanToInt("LVIII") << endl;
    cout << romanToInt("MCMXCIV") << endl;
}

Output:
3
58
1994

Code explanation

1. The unordered_map value is a constant mapping from Roman numeral characters to their corresponding integer values.
2. The function romanToInt takes a string s as input, representing a Roman numeral.
3. The function initializes two variables: i is set to the last index of the string s, and result is initialized with the integer value of the last Roman numeral character in the string.
4. A while loop iterates through the string from the second-to-last character to the first character.
5. Inside the loop, the code checks if the value of the current character (s[i]) is less than the value of the next character (s[i+1]). If true, it subtracts the value of the current character from the result; otherwise, it adds the value.
6. The loop continues until it reaches the beginning of the string.
7. The final result is the integer equivalent of the given Roman numeral string, and it is returned by the function.

This code essentially implements the rules of Roman numeral conversion, where a smaller numeral before a larger numeral is subtracted, and a smaller numeral after a larger numeral is added.

Complexity

This solution efficiently converts a Roman numeral string into an integer by iterating through the string from right to left and applying the rules of Roman numerals, where subtractive combinations are subtracted and additive combinations are added to calculate the total value. The unordered map is used to look up the values of Roman numerals.

• Runtime: O(N) where N = s.length.
• Extra space: O(1).

Thanks for reading!

I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!

Nhut Nguyen, the author of The Problem Solver's Guide To Coding.