{x}
blog image

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9. 
  • X can be placed before L (50) and C (100) to make 40 and 90. 
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

 

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 Explanation: Roman to Integer

This problem involves converting a Roman numeral string into its integer equivalent. Roman numerals use a combination of seven symbols (I, V, X, L, C, D, M) to represent numbers. A key aspect is that some symbols are subtractive (e.g., IV = 4, IX = 9), while others are additive (e.g., III = 3, VI = 6).

Approach

The most efficient approach uses a hash table (or dictionary in Python) to store the integer values of each Roman numeral symbol. The solution then iterates through the input string, comparing the value of each symbol with the value of the next symbol.

  • If the current symbol's value is less than the next symbol's value, it's a subtractive case. Subtract the current symbol's value from the running total.
  • Otherwise, it's an additive case. Add the current symbol's value to the running total.

After iterating through the entire string, the final running total represents the integer equivalent of the Roman numeral.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input Roman numeral string. The algorithm iterates through the string once.
  • Space Complexity: O(1). The hash table has a constant size (7 entries for the Roman numeral symbols), regardless of the input string's length.

Code Implementation (Python)

def roman_to_int(roman_string):
    """Converts a Roman numeral string to an integer.
 
    Args:
        roman_string: The Roman numeral string to convert.
 
    Returns:
        The integer equivalent of the Roman numeral.
        Returns -1 if the input is invalid.
 
    """
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    
    if not all(c in roman_map for c in roman_string):
        return -1 #Handle invalid input
 
    result = 0
    prev_value = 0
    for i in range(len(roman_string) - 1, -1, -1):  # Iterate from right to left
        current_value = roman_map[roman_string[i]]
        if current_value < prev_value:
            result -= current_value
        else:
            result += current_value
        prev_value = current_value
    return result
 
# Example Usage
print(roman_to_int("III"))   # Output: 3
print(roman_to_int("LVIII"))  # Output: 58
print(roman_to_int("MCMXCIV")) # Output: 1994
print(roman_to_int("IX")) #Output: 9
print(roman_to_int("Invalid")) #Output: -1

The code iterates through the Roman numeral string from right to left. This simplifies the handling of subtractive cases because we only need to check if the current value is less than the previously processed value. Invalid inputs are also handled returning -1

The code in other languages provided in the original response follows a similar approach, with variations in syntax and data structure usage (hash map, dictionary, etc.) but the core logic remains consistent.