We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Roman to Integer

Number: 13

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Microsoft, Bloomberg, Oracle, Expedia, Adobe, AMD, Pwc, Goldman Sachs, tcs, Accenture, IBM, LinkedIn, Apple, Salesforce, Zoho, Wix, Uber, Yahoo, RBC, Capital One, SoFi

Problem Description

Given a string representing a Roman numeral, convert it to its integer equivalent. Roman numerals are represented by seven symbols, and in some cases, a smaller numeral appears before a larger numeral to indicate subtraction. For example, "MCMXCIV" converts to 1994.

Key Insights

  • Map each Roman numeral character to its integer value using a hash table or dictionary.
  • Loop through the string and check if the current numeral is less than the next numeral; if so, subtract its value.
  • Otherwise, add its value to the total.
  • This approach takes advantage of the subtractive notation used in Roman numerals.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1), since the mapping and additional variables use constant space.

Solution

We use a dictionary (or hash map) to store the values of each Roman numeral. As we iterate over the string, we compare the current numeral's value with the next numeral's value. When a numeral of smaller value appears before a numeral of larger value, we subtract the current numeral's value; otherwise, we add it. This technique efficiently handles both the standard and subtractive cases in one pass through the string.

Code Solutions

# Define a function to convert Roman numeral to integer
def romanToInt(s):
    # Map each Roman numeral to its integer value
    roman_values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0  # Initialize the total integer value
    
    # Loop over the string using index
    for i in range(len(s)):
        # If this is not the last character and the current value is less than the next value,
        # subtract the current value; otherwise, add the current value.
        if i + 1 < len(s) and roman_values[s[i]] < roman_values[s[i + 1]]:
            total -= roman_values[s[i]]
        else:
            total += roman_values[s[i]]
    return total

# Example usage:
print(romanToInt("MCMXCIV"))  # Output: 1994
← Back to All Questions