Problem Statement: Roman to Integer
The task is to convert a given Roman numeral to its corresponding integer value. Roman numerals are written by combining symbols, and a smaller numeral placed before a larger numeral means subtraction. For example:
IV= 4 (5 – 1)IX= 9 (10 – 1)XL= 40 (50 – 10)XC= 90 (100 – 10)CD= 400 (500 – 100)CM= 900 (1000 – 100)
You are to implement a function that converts a given Roman numeral string into an integer.
Roman Numeral Symbols:
I= 1V= 5X= 10L= 50C= 100D= 500M= 1000
Example:
Input:
"III"
Output:
3
Input:
"IV"
Output:
4
Input:
"IX"
Output:
9
Input:
"LVIII"
Output:
58
Input:
"MCMXCIV"
Output:
1994
Approach:
- Initialize a Mapping of Roman Symbols to Values:
- Use a dictionary or a set of key-value pairs to map Roman numerals to their integer values.
- Iterate Through the Roman Numeral String:
- Traverse the Roman numeral string from left to right.
- If the value of the current symbol is less than the value of the next symbol, subtract the current symbol’s value (i.e., handle cases like
IV,IX, etc.). - Otherwise, simply add the value of the current symbol.
- Sum the Values:
- The final result will be the total sum of the values after the traversal.
- Edge Case:
- Handle the smallest Roman numeral (
I) and the largest valid Roman numeral (MMMCMXCIX= 3999).
- Handle the smallest Roman numeral (
Time Complexity:
- Time Complexity: O(n)O(n)O(n), where nnn is the length of the Roman numeral string (since we are iterating through the string once).
- Space Complexity: O(1)O(1)O(1), as the space used does not depend on the input size, only on the Roman numeral value mapping.
Code Implementation
C Code:
include <stdio.h>
#include <string.h>
int romanToInt(char *s) {
// Roman numeral to integer mappings
int roman[] = {1000, 500, 100, 50, 10, 5, 1};
char *romans[] = {"M", "D", "C", "L", "X", "V", "I"};
int result = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
int value = 0;
// Find the value of current character
for (int j = 0; j < 7; j++) {
if (s[i] == romans[j][0]) {
value = roman[j];
break;
}
}
// If next character represents a larger value, subtract the current value
if (i < len - 1) {
int nextValue = 0;
for (int j = 0; j < 7; j++) {
if (s[i + 1] == romans[j][0]) {
nextValue = roman[j];
break;
}
}
if (value < nextValue) {
result -= value;
} else {
result += value;
}
} else {
result += value;
}
}
return result;
}
int main() {
char s[] = "MCMXCIV";
printf("Integer value of %s is: %d\n", s, romanToInt(s)); // Output: 1994
return 0;
}
C++ Code:
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int romanToInt(string s) {
unordered_map<char, int> romanMap = {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100},
{'D', 500}, {'M', 1000}
};
int result = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
int value = romanMap[s[i]];
// If the next character represents a larger value, subtract the current value
if (i < len - 1 && value < romanMap[s[i + 1]]) {
result -= value;
} else {
result += value;
}
}
return result;
}
int main() {
string s = "MCMXCIV";
cout << "Integer value of " << s << " is: " << romanToInt(s) << endl; // Output: 1994
return 0;
}
Java Code:
import java.util.HashMap;
public class Solution {
public int romanToInt(String s) {
// Roman numeral to integer mapping
HashMap<Character, Integer> romanMap = new HashMap<>();
romanMap.put('I', 1);
romanMap.put('V', 5);
romanMap.put('X', 10);
romanMap.put('L', 50);
romanMap.put('C', 100);
romanMap.put('D', 500);
romanMap.put('M', 1000);
int result = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
int value = romanMap.get(s.charAt(i));
// If next character represents a larger value, subtract the current value
if (i < len - 1 && value < romanMap.get(s.charAt(i + 1))) {
result -= value;
} else {
result += value;
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "MCMXCIV";
System.out.println("Integer value of " + s + " is: " + solution.romanToInt(s)); // Output: 1994
}
}
Python Code:
def romanToInt(s: str) -> int:
roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
result = 0
length = len(s)
for i in range(length):
value = roman_map[s[i]]
# If next character represents a larger value, subtract the current value
if i < length - 1 and value < roman_map[s[i + 1]]:
result -= value
else:
result += value
return result
# Example Usage
s = "MCMXCIV"
print(f"Integer value of {s} is: {romanToInt(s)}") # Output: 1994
C# Code:
using System;
using System.Collections.Generic;
public class Solution {
public int RomanToInt(string s) {
// Roman numeral to integer mapping
var romanMap = new Dictionary<char, int> {
{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100},
{'D', 500}, {'M', 1000}
};
int result = 0;
int len = s.Length;
for (int i = 0; i < len; i++) {
int value = romanMap[s[i]];
// If next character represents a larger value, subtract the current value
if (i < len - 1 && value < romanMap[s[i + 1]]) {
result -= value;
} else {
result += value;
}
}
return result;
}
public static void Main() {
Solution solution = new Solution();
string s = "MCMXCIV";
Console.WriteLine($"Integer value of {s} is: {solution.RomanToInt(s)}"); // Output: 1994
}
}
JavaScript Code:
var romanToInt = function(s) {
const romanMap = {
'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000
};
let result = 0;
let length = s.length;
for (let i = 0; i < length; i++) {
let value = romanMap[s[i]];
// If next character represents a larger value, subtract the current value
if (i < length - 1 && value < romanMap[s[i + 1]]) {
result -= value;
} else {
result += value;
}
}
return result;
};
console.log(romanToInt("MCMXCIV")); // Output: 1994
Summary:
- The solution works by iterating through the Roman numeral string and applying the rules of subtraction for cases where a smaller numeral precedes a larger one.
- Time Complexity: O(n)O(n)O(n), where nnn is the length of the Roman numeral string.
- Space Complexity: O(1)O(1)O(1), since the space used is constant, independent of the input size.