Algorithm – Roman To Integer

What is required?

Given a roman numeral, convert it to integer.

Discussion

Roman numerals are a numeral system that was used in ancient Rome and other parts of the Roman Empire. They are based on a combination of letters from the Latin alphabet. Here are the basic symbols used in Roman numerals and their corresponding values

These symbols can be combined to represent different numbers. The rules for constructing Roman numerals are as follows:

1. Symbols are combined from left to right, and the values are added together to get the total value.
   • For example, “VIII” represents 5 + 1 + 1 + 1 = 8.
2. If a smaller value symbol appears before a larger value symbol, the smaller value is subtracted from the larger value.
   • For example, “IV” represents 5 – 1 = 4.
   • Similarly, “IX” represents 10 – 1 = 9.
3. A symbol can be repeated up to three times in a row to represent its value.
   • For example, “III” represents 1 + 1 + 1 = 3.
   • However, the symbols for 5, 50, 500 (V, L, D) cannot be repeated.
4. To represent larger numbers, a horizontal bar is placed above a symbol, indicating multiplication by 1000.
   • For example, “M” represents 1000, and “MM” represents 1000 + 1000 = 2000.
   • The largest number that can be represented using Roman numerals is 3,999 (MMMCMXCIX).

Roman numerals do not have a symbol for zero or negative numbers.

Discussion

Lets dive into the algorithm logic and explain each step

1. Initialize a variable finalAnswer to hold the resulting integer value
2. Iterate over the characters of the input string s from right to left using a for loop.
3. Inside the loop, a switch statement is used to handle each Roman numeral character.
4. For each character, the corresponding value is added to the finalAnswer variable based on the following rules:
   • ‘M’: Add 1000 to finalAnswer.
   • ‘D’: Add 500 to finalAnswer.
   • ‘C’: Add 100 to finalAnswer if the current finalAnswer is less than 500; otherwise, subtract 100 from finalAnswer.
   • ‘L’: Add 50 to finalAnswer.
   • ‘X’: Add 10 to finalAnswer if the current finalAnswer is less than 50; otherwise, subtract 10 from finalAnswer.
   • ‘V’: Add 5 to finalAnswer.
   • ‘I’: Add 1 to finalAnswer if the current finalAnswer is less than 5; otherwise, subtract 1 from finalAnswer.
5. After iterating through all the characters in the input string, return the finalAnswer as the resulting integer value.

Time Complexity

The time complexity of this code is O(n), where n is the length of the input string s. This is because the code iterates through each character of the input string once. The switch statement has constant time complexity for each case.

Java code implementation

public int romanToInt(String s) {
        int finalAnswer = 0;

        for (int i = s.length() - 1; i >= 0; i--) {

            switch (s.charAt(i)) {
                case 'M':
                    finalAnswer += 1000;
                    break;
                case 'D':
                    finalAnswer += 500;
                    break;
                case 'C':
                    finalAnswer += 100 * (finalAnswer >= 500 ? -1 : 1);
                    break;
                case 'L':
                    finalAnswer += 50;
                    break;    
                case 'X':
                    finalAnswer += 10 * (finalAnswer >= 50 ? -1 : 1);
                    break;
                case 'V':
                    finalAnswer += 5;
                    break;
                case 'I':
                    finalAnswer += (finalAnswer >= 5 ? -1 : 1); // I = 1 in romans
                    break;
                default:
                    break;
            }
        }

        return finalAnswer;
    }

Python implementation

C++ implementation

 int romanToInt(string s) {
        int finalAnswer = 0;

    for (int i = s.length() - 1; i >= 0; i--) {
        switch (s[i]) {
            case 'M':
                finalAnswer += 1000;
                break;
            case 'D':
                finalAnswer += 500;
                break;
            case 'C':
                finalAnswer += 100 * (finalAnswer >= 500 ? -1 : 1);
                break;
            case 'L':
                finalAnswer += 50;
                break;
            case 'X':
                finalAnswer += 10 * (finalAnswer >= 50 ? -1 : 1);
                break;
            case 'V':
                finalAnswer += 5;
                break;
            case 'I':
                finalAnswer += (finalAnswer >= 5 ? -1 : 1);
                break;
            default:
                break;
        }
    }

    return finalAnswer;
    }

C# implementation

public int RomanToInt(string s) {
        int finalAnswer = 0;

        for (int i = s.Length - 1; i >= 0; i--)
        {
            switch (s[i])
            {
                case 'M':
                    finalAnswer += 1000;
                    break;
                case 'D':
                    finalAnswer += 500;
                    break;
                case 'C':
                    finalAnswer += 100 * (finalAnswer >= 500 ? -1 : 1);
                    break;
                case 'L':
                    finalAnswer += 50;
                    break;
                case 'X':
                    finalAnswer += 10 * (finalAnswer >= 50 ? -1 : 1);
                    break;
                case 'V':
                    finalAnswer += 5;
                    break;
                case 'I':
                    finalAnswer += (finalAnswer >= 5 ? -1 : 1);
                    break;
                default:
                    break;
            }
        }

        return finalAnswer;
   
    }

Check out my other article of finding the Length Of The Longest Substring Without Repeating Characters here

Our Facebook page is here. You can also find our youtube channel here.