Roman to Integer Conversion

The challenge is to translate a Roman string entered into roman form into an integer.

The symbols I, V, X, L, C, D, and M define 1, 5, 10, 50, 100, 500, and 1,000, respectively, so Roman numerals are based on these symbols. Various ways these symbols are arranged show different numbers. Roman numerals I, II, III, IV, V, VI, VII, VIII, IX, and X correspond, respectively, 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10.

How did the conversion go?

Should a higher value symbol precede, we deduct. In other cases, we add.
In IV I precedes V, and V has a higher value—five. Our answer is thus 5 – 1 = 4.
In VI, V occurs before I and I has a smaller value 1. Our answer then is 5 + 1 = 6.
In II, we have equal values; so, we add and get 1 + 1 = 2.
When more than two characters are involved, we move from left to right and group just when we come upon a larger value character following a lower. MXVII for instance is 1000 + 10 + 5 + 1 + 1 = 1017. XLVII also equals (50 – 10) + 5 + 1 + 1 = 47. L is bigger and comes after X, though.

Example:

Using Iterative Comparison – O(n) time and O(1) space

Turning a Roman numeral into an integer requires us to walk the string from left to right. For every symbol, pair it with the following symbol—if one exists. Add the value of the current symbol to the resultant value if it is either more than or equal to the following symbol. Otherwise, skip the next symbol and subtract its value from the value of the following symbol then add the resultant total.

The thorough guidelines for above intuition are found below:

• Starting a result variable at 0
• Go left to right iteratively over the string.
• Get the matching value for every character and compare the value of the present symbol with the value of the next symbol (should one exist).
• Add the current value to the output whether it is more than or equal to the next value.
• Add the difference (next value – current value) to the result if the current value is smaller than the next value; skip the next symbol instead.
• Get back the outcome after handling every symbol.

C++

#include <bits/stdc++.h>
using namespace std;

// This function returns value of a Roman symbol
int value(char r)
{
    if (r == 'I')
        return 1;
    if (r == 'V')
        return 5;
    if (r == 'X')
        return 10;
    if (r == 'L')
        return 50;
    if (r == 'C')
        return 100;
    if (r == 'D')
        return 500;
    if (r == 'M')
        return 1000;
    return -1;
}

// Returns decimal value of roman numeral
int romanToDecimal(string& str)
{
    int res = 0; // Initialize result

    for (int i = 0; i < str.length(); i++) {
        // Get value of current symbol
        int s1 = value(str[i]);

        // Compare with the next symbol if it exists
        if (i + 1 < str.length()) {
            int s2 = value(str[i + 1]);

            // If current value is greater or equal, add it
            // to result
            if (s1 >= s2) {
                res += s1;
            }
            else {
                // Else, add the difference and skip next
                // symbol
                res += (s2 - s1);
                i++;
            }
        }
        else {
            res += s1;
        }
    }

    return res;
}

// Driver code
int main()
{
    string str = "IX";
    cout << romanToDecimal(str) << endl;
    return 0;
}

Java

public class RomanToDecimal {
    // This function returns the value of a Roman symbol
    public static int value(char r)
    {
        if (r == 'I')
            return 1;
        if (r == 'V')
            return 5;
        if (r == 'X')
            return 10;
        if (r == 'L')
            return 50;
        if (r == 'C')
            return 100;
        if (r == 'D')
            return 500;
        if (r == 'M')
            return 1000;
        return -1;
    }

    // Returns the decimal value of a Roman numeral
    public static int romanToDecimal(String str)
    {
        int res = 0; // Initialize the result
        for (int i = 0; i < str.length(); i++) {

            // Get the value of the current symbol
            int s1 = value(str.charAt(i));
            if (i + 1 < str.length()) {

                // Get the value of the next symbol
                int s2 = value(str.charAt(i + 1));
                if (s1 >= s2) {

                    // If the current value is greater or
                    // equal, add it to the result
                    res += s1;
                }
                else {

                    // Else, add the difference and skip the
                    // next symbol
                    res += (s2 - s1);
                    i++;
                }
            }
            else {

                // Add the last symbol to the result
                res += s1;
            }
        }
        return res;
    }

    public static void main(String[] args)
    {
        String str = "IX";
        System.out.println(romanToDecimal(str));
    }
}

Python

# This function returns value of a Roman symbol
def value(r: str) -> int:
    if r == 'I':
        return 1
    if r == 'V':
        return 5
    if r == 'X':
        return 10
    if r == 'L':
        return 50
    if r == 'C':
        return 100
    if r == 'D':
        return 500
    if r == 'M':
        return 1000
    return -1

# Returns decimal value of Roman numeral


def romanToDecimal(s: str) -> int:
    res = 0  # Initialize result

    i = 0
    while i < len(s):
        # Get value of current symbol
        s1 = value(s[i])

        # Compare with the next symbol if it exists
        if i + 1 < len(s):
            s2 = value(s[i + 1])

            # If current value is greater or equal,
            # add it to result
            if s1 >= s2:
                res += s1
            else:
                # Else, add the difference and skip
                # next symbol
                res += (s2 - s1)
                i += 1
        else:
            res += s1
        i += 1

    return res


# Driver code
if __name__ == "__main__":
    s = "IX"
    print(romanToDecimal(s))

JS

// This function returns the value of a Roman symbol
function value(r) {
  if (r === 'I') return 1;
  if (r === 'V') return 5;
  if (r === 'X') return 10;
  if (r === 'L') return 50;
  if (r === 'C') return 100;
  if (r === 'D') return 500;
  if (r === 'M') return 1000;
  return -1;
}

// Returns the decimal value of a Roman numeral
function romanToDecimal(str) {

  let res = 0; // Initialize the result
  for (let i = 0; i < str.length; i++) {
  
    // Get the value of the current symbol
    let s1 = value(str[i]);
    if (i + 1 < str.length) {
    
      // Get the value of the next symbol
      let s2 = value(str[i + 1]);
      if (s1 >= s2) {
      
        // If the current value is greater
        // or equal, add it to the result
        res += s1;
      } else {
      
        // Else, add the difference and skip
        // the next symbol
        res += (s2 - s1);
        i++;
      }
    } else {
    
      // Add the last symbol to the result
      res += s1;
    }
  }
  return res;
}

console.log(romanToDecimal("IX"));

Output

9

Time Complexity: O(n), where n is the length of the string. Only one traversal of the string is required.
Auxiliary Space: O(1), As no extra space is required.

Read More: [Expected Approach-2] Using Hashing– O(n) time and O(1) space