Roman To Integer

Solution For Roman To Integer

Problem Statement:

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 one’s 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

Example 2:

Input: s = “IV”
Output: 4

Example 3:

Input: s = “IX”
Output: 9

Example 4:

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

Example 5:

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].

Approach:

To solve this problem, we can use the following steps:

  1. Create a dictionary to store the integer values of each roman numeral symbol.

  2. Initialize a variable ‘number’ to zero.

  3. Traverse through the roman numeral string and check the current symbol and the next symbol to determine if it is a subtrahend.

  4. If it is a subtrahend, subtract the current symbol value from the next symbol value and add it to the ‘number’ variable.

  5. If it is not a subtrahend, simply add the current symbol value to the ‘number’ variable.

  6. Return the ‘number’ variable.

Code:

Here is the Python 3 code implementing the above approach:

class Solution:
def romanToInt(self, s: str) -> int:
# create a dictionary to store the integer values of each roman numeral symbol
roman_dict = {‘I’: 1, ‘V’: 5, ‘X’: 10, ‘L’: 50, ‘C’: 100, ‘D’: 500, ‘M’: 1000}

    # initialize a variable 'number' to zero
    number = 0

    # traverse through the roman numeral string
    for i in range(len(s)):
        # check the current symbol and the next symbol to determine if it is a subtrahend
        if i < len(s) - 1 and roman_dict[s[i]] < roman_dict[s[i+1]]:
            # subtract the current symbol value from the next symbol value and add it to the 'number' variable
            number -= roman_dict[s[i]]
        else:
            # simply add the current symbol value to the 'number' variable
            number += roman_dict[s[i]]

    # return the 'number' variable
    return number

Time Complexity Analysis:

The time complexity of the above code is O(n) where n is the length of the input roman numeral string.

This is because we traverse through the string once and perform constant time operations for each symbol.

Hence, the time complexity of the algorithm is linear in the length of the input string.

Space Complexity Analysis:

The space complexity of the above code is O(1) because we use a dictionary to store the integer values of each Roman numeral symbol.

The size of the dictionary is constant, and does not depend on the length of the input string.

Therefore, the space complexity of the algorithm is constant.

Step by Step Implementation For Roman To Integer

public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0)
            return 0;
        Map map = new HashMap();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int len = s.length(), result = map.get(s.charAt(len - 1));
        for (int i = len - 2; i >= 0; i--) {
            if (map.get(s.charAt(i + 1)) <= map.get(s.charAt(i)))
                result += map.get(s.charAt(i));
            else
                result -= map.get(s.charAt(i));
        }
        return result;
    }
}
def romanToInt(s):
    
    # create a dictionary of key/value pairs for Roman numerals
    roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    
    # initialize result
    result = 0
    
    # loop through the string, starting at the beginning
    for i in range(0, len(s)):
        
        # if the current value is less than the next value
        if i < len(s) - 1 and roman[s[i]] < roman[s[i+1]]:
            
            # subtract the current value
            result -= roman[s[i]]
            
        # otherwise, add the current value
        else:
            result += roman[s[i]]
            
    return result
// 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, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven 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. Input is guaranteed to be within the range from 1 to 3999.

// Example 1:

// Input: "III"
// Output: 3
// Example 2:

// Input: "IV"
// Output: 4
// Example 3:

// Input: "IX"
// Output: 9
// Example 4:

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

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


var romanToInt = function(s) {
    // create a hashmap of roman numerals and their corresponding integers
    let hashmap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    // create a variable to store the integer value of the roman numeral
    let integer = 0
    
    // iterate through the roman numeral string
    for (let i = 0; i < s.length; i++) {
        // if the current roman numeral is less than the next roman numeral in the string, we need to subtract the current value from the integer
        if (hashmap[s[i]] < hashmap[s[i+1]]) {
            integer -= hashmap[s[i]]
        // otherwise, we can just add the current value to the integer
        } else {
            integer += hashmap[s[i]]
        }
    }
    
    // return the integer value of the roman numeral
    return integer
};
int romanToInt(string s) {
        unordered_map T = { { 'I' , 1 },
                                       { 'V' , 5 },
                                       { 'X' , 10 },
                                       { 'L' , 50 },
                                       { 'C' , 100 },
                                       { 'D' , 500 },
                                       { 'M' , 1000 } };
                                       
        int sum = T[s.back()];
        for (int i = s.length() - 2; i >= 0; --i) 
        {
            if (T[s[i]] < T[s[i + 1]])
            {
                sum -= T[s[i]];
            }
            else
            {
                sum += T[s[i]];
            }
        }
        
        return sum;
    }
public class Solution {
    public int RomanToInt(string s) {
        //Create a dictionary to store all of the Roman numerals and their corresponding integer values
        Dictionary romanNumerals = new Dictionary();
        romanNumerals.Add('I', 1);
        romanNumerals.Add('V', 5);
        romanNumerals.Add('X', 10);
        romanNumerals.Add('L', 50);
        romanNumerals.Add('C', 100);
        romanNumerals.Add('D', 500);
        romanNumerals.Add('M', 1000);
        
        //Create a variable to store the final integer value
        int result = 0;
        
        //Loop through the string, starting at the end
        for(int i = s.Length - 1; i >= 0; i--){
            //If the current character is the last character in the string, or if the current character has a greater value than the next character,
            //add the corresponding integer value to the result
            if(i == s.Length - 1 || romanNumerals[s[i]] >= romanNumerals[s[i + 1]]){
                result += romanNumerals[s[i]];
            }
            //If the current character has a smaller value than the next character, subtract the corresponding integer value from the result
            else{
                result -= romanNumerals[s[i]];
            }
        }
        
        return result;
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]