Convert Roman Number to Corresponding Integer Value

Difficulty: Easy, Asked-in: Amazon, Microsoft, Facebook

Key takeaway: An excellent problem to learn problem-solving using loop.

Let’s understand the problem

Given a Roman numeral, write a program to find its corresponding decimal value. Roman numerals are represented by seven different symbols:

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

Problem Note

• The input contains only the characters 'I', 'V', 'X', 'L', 'C', 'D', 'M'.
• Input is a valid roman numeral in the range [1, 3999].
• A number in Roman numerals is a string of these symbols written in descending order i.e. largest to smallest from left to right. 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 XXVII, which is XX + V + II.
• We avoid four characters being repeated in successions such as IIII or VIIII. Instead, the number four is written as IV because the 1 is before the 5, and we subtract it making 4. The same principle applies to number 9, which is written as IX. The idea is: when there is a smaller number placed before a larger number, the values are subtracted.

Example 1: Input: XL, Output: 40

Explanation: XL is a Roman symbol which represents 40

Example 2: Input: MCMIV, Output: 1904

Explanation: M = 1000, CM = 900, IV = 4

Example 3: Input: LVIII, Output: 58

Explanation: L = 50, V= 5, III = 3

Example 4: Input: MCMXCIV, Output: 1994

Explanation: M = 1000, CM = 900, XC = 90 and IV = 4

Solution using a single loop

Solution idea and steps

According to the properties of the Roman numbers, two conditions will appear for any substring of the given input: 

• Case 1 : The string of symbols will appear in descending order or three characters being repeated in successions.
• Case 2 : The smaller Roman number is placed before a larger number or four characters is not repeated in the successions.

One solution idea would be to scan the input string and incrementally generate the integer value based on the appearance of case 1 and case 2 . Suppose function romanToInteger(String S, int n) is converting a roman string S of size n to its integer value.

Step 1: We declare variable output to store the integer value of the given roman string.

Step 2: Now we scan the input string using a loop. Inside the loop: We declare two variables curr and next to track the integer value of two consecutive roman characters at index i and i + 1. We are using a helper function integerValues(char c) to get the integer value of a roman character.

• If (curr >= next): This is a situation of case 1. So we add the curr value to the output i.e. output = output + curr.
• If (curr < next): This is a situation of case 2. So we add next - curr to the output i.e. output = output + (next - curr). Here (next - curr) is the combined integer value of the two roman characters, so we also increment the value of i by 1. Note: we are also incrementing i in the loop.
• Boundary condition: before calculating the value of next, we need to check: do we present at the last index? If yes, then there is no need to calculate next and we just add the curr to the output i.e. output = output + curr.

Step 3: By end of the loop, we return the value stored in the variable output.

Solution code C++

int integerValue(char c)
{
    if (c == 'I')
        return 1;
    if (c == 'V')
        return 5;
    if (c == 'X')
        return 10;
    if (c == 'L')
        return 50;
    if (c == 'C')
        return 100;
    if (c == 'D')
        return 500;
    if (c == 'M')
        return 1000;
    return -1;
}

int romanToInteger(string S, int n)
{
    int output = 0;
    for (int i = 0; i < n; i = i + 1) 
    {
        int curr = integerValue(S[i]);
        if (i + 1 < n) 
        {
            int next = integerValue(S[i + 1]);
            if (curr >= next)
                output = output + curr;
            else
            {
                output = output + next - curr;
                i = i + 1;
            }
        }
        else
            output = output + curr;
    }
    return output;
}

Solution code Python

def integerValue(c):
    if c == 'I':
        return 1
    if c == 'V':
        return 5
    if c == 'X':
        return 10
    if c == 'L':
        return 50
    if c == 'C':
        return 100
    if c == 'D':
        return 500
    if c == 'M':
        return 1000
    return -1

def romanToInteger(S, n):
    output = 0
    for i in range(n):
        curr = integerValue(S[i])
        if i + 1 < n:
            next = integerValue(S[i + 1])
            if curr >= next:
                output = output + curr
            else:
                output = output + next - curr
                i = i + 1
        else:
            output = output + curr
    return output

Another solution idea similar to the above approach

From the Roman string of a number, we can observe one thing: there is only one smaller number before a larger number. Or in other words, there will be at max two Roman characters will be in increasing order. So another basic idea would be:

• Access each roman character using a loop and check the current character is less than the next character or not. If yes, then we subtract the integer value of the current character from the overall output.
• Otherwise, we add the integer value of the current character from the overall output. This would be the scenario when string symbols will appear in descending order or three characters being repeated in successions.
• We need to take care of the boundary condition when we reach the last character.

Solution code C++

int integerValue(char c)
{
    if (c == 'I')
        return 1;
    if (c == 'V')
        return 5;
    if (c == 'X')
        return 10;
    if (c == 'L')
        return 50;
    if (c == 'C')
        return 100;
    if (c == 'D')
        return 500;
    if (c == 'M')
        return 1000;
    return -1;
}

int romanToInteger(string S, int n)
{
    int output = 0;
    for(int i = 0; i < n; i = i + 1)
    {
        int curr = integerValue(S[i]);
        if(i + 1 < n)
        {
            int next = integerValue (S[i+1]);
            if(curr >= next)
                output = output + curr;
            else
                output = output - curr;
        }
        else 
            output = output + curr;
    }
    
    return output;
}

Solution code Python

def integerValue(c):
    if c == 'I':
        return 1
    if c == 'V':
        return 5
    if c == 'X':
        return 10
    if c == 'L':
        return 50
    if c == 'C':
        return 100
    if c == 'D':
        return 500
    if c == 'M':
        return 1000
    return -1

def romanToInteger(S, n):
    output = 0
    for i in range(n):
        curr = integerValue(S[i])
        if i + 1 < n:
            next = integerValue(S[i + 1])
            if curr >= next:
                output = output + curr
            else:
                output = output - curr
        else:
            output = output + curr
    return output

Solution analysis

In both approaches, we are running a single loop and doing O(1) operations at each iteration. So time complexity = n * O(1) = O(n). We are using a constant number of variables, so space complexity = O(1).

Critical ideas to think!

• Can we solve this problem using some other approach?
• Can we think to optimize the above code further?
• Can we think about solving this problem recursively?
• Instead of using the helper function integerValue(char c), can we implement the above solution using switch statements or an unordered map?
• Which solution will perform less number of operations?

Suggested problems to practice

• Convert integer to English words
• Convert a decimal number to Roman numerals
• Validate Roman numerals using regular expression
• Find the largest roman numeral possible by rearranging characters of a string

Enjoy learning, Enjoy algorithms!