Roman to Integer

5
0

Given a string s representing a Roman numeral, convert it into its corresponding integer value.

Roman numerals consist of seven different symbols, each having a fixed value:

  • I = 1

  • V = 5

  • X = 10

  • L = 50

  • C = 100

  • D = 500

  • M = 1000

Roman numerals are generally written from larger values to smaller values, from left to right. However, in certain cases, a smaller symbol placed before a larger symbol represents subtraction instead of addition.

The following combinations follow this rule:

  • IV = 4 and IX = 9

  • XL = 40 and XC = 90

  • CD = 400 and CM = 900

For all other valid combinations, the values of the symbols are added together.

Return the integer represented by the given Roman numeral.

Example 1

Input: s = "XLII"

Output: 42

Explanation: The combination XL represents 40 because X appears before L. The remaining II represents 2. Hence, the final value is 40 + 2 = 42.

Example 2

Input: s = "MCMXCIV"

Output: 1994

Explanation: The Roman numeral can be divided into M = 1000, CM = 900, XC = 90, and IV = 4. Adding these values gives 1000 + 900 + 90 + 4 = 1994.

Approach

Roman numerals follow a simple addition rule in most cases, where the value of each symbol contributes to the final number. The only exception occurs when a smaller symbol appears before a larger one. In such cases, the smaller value is subtracted instead of added. For example, IV represents 4 rather than 6.

A comparison with the next symbol helps identify these special cases. If the current symbol has a smaller value than the next one, its value is subtracted; otherwise, it is added. Applying this rule while moving through the string gives the final integer.

Algorithm

  • Create a mapping between each Roman symbol and its corresponding integer value.

  • Traverse the given string from left to right.

  • Get the integer value of the current Roman symbol.

  • Check the next symbol, if one exists.

  • If the current value is smaller than the next value, subtract it from the result.

  • Otherwise, add the current value to the result.

  • Return the final accumulated value after processing all symbols.

Dry Run

Roman to Integer

Roman to Integer

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Converts a Roman numeral into an integer.
int romanToInt(string s) {
unordered_map<char, int> romanValues = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int result = 0;
// Visit every symbol in the Roman numeral.
for (int index = 0; index < s.size(); index++) {
int currentValue = romanValues[s[index]];
/*
Subtract the current value when a larger
Roman symbol appears immediately after it.
*/
if (
index + 1 < s.size() &&
currentValue < romanValues[s[index + 1]]
) {
result -= currentValue;
}
// Add the current value in every other case.
else {
result += currentValue;
}
}
return result;
}
};
// Driver Code starts
int main() {
string s = "XLII";
Solution solution;
// Call the function to convert the Roman numeral.
int answer = solution.romanToInt(s);
cout << answer << "\n";
return 0;
}

Complexity Analysis

• Time Complexity: O(N) as the algorithm traverses the Roman numeral string once, performing constant-time hashmap lookups and comparisons for each character.

• Space Complexity: O(1), because the hashmap stores exactly seven Roman numeral symbols, requiring constant extra space regardless of the input length.

Interview follow-up Questions

No. Standard Roman numerals use uppercase symbols such as I, V, X, and M. Lowercase input would require conversion to uppercase before processing.

StringTCS NQT

Read Similar Blogs

Comments0