Roman to Integer Leetcode Solution Roman Integer

In the problem “Roman to Integer”, we are given a string representing some positive integer in its Roman numeral form. Roman numerals are represented by 7 characters that can be converted to integers using the following table:

Note: The integer value of the given roman numeral will not exceed or equal the value 4000.

Table of Contents

Example

IX

CXXIX

Explanation #1

IX is 9 in integers

Explanation #2

CXXIX = C + XX + IX = 100 + 20 + 9 = 129

Approach(Left to Right Pass)

We can do a left to right pass in the array, and keep adding the corresponding value for every character in it. But, the peculiar aspect of roman numerals is if a character of less integer value occurs before that of a high value, the result is not their distinct sum.

For example, IX in roman should equal 1 + 10 = 11 if we added characters subsequently. But, IX = 9, as I that occurs before X is less in integral value. So, the result is treated as I subtracted from X. Hence, IX = 9.

Therefore, we can’t add the integer value of every character in the string simply. We also need to check the character next to it, for the above-mentioned case. In this way, we can convert the given roman numeral string into the required integer.

Algorithm

Create a function getInteger() to return the value of a single roman character passed to it using switch cases
Initialize result to store required integer
Again, initialize current and next to store the value of current and next integer values of respective characters in the string for every iteration
Iterate for i = 0 until i < N (N = size of the array)
- If i is the last index of the array, we have no next character, so add integer value of String[i] and return result
- Retrieve the integer value of current and next characters using getInteger()
- If current <= next
  - Add current to the result
  - Increment i by 1, i.e., i++
- Else
  - Add next – current to the result
  - Increment i by 2, i.e, i += 2
Print the result

Implementation of Roman to Integer Leetcode Solution

C++ Program

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

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size() , result = 0 , current , next , i = 0;
    while(i < n)
    {
        if(i == n - 1)
        {
            result += getInteger(s[i]);
            return result;
        }
        current = getInteger(s[i]) , next = getInteger(s[i + 1]);
        if(current >= next)
            result += current , i++;
        else
            result += next - current , i += 2;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

Java Program

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length() , result = 0 , current , next , i = 0;
        while(i < n)
        {
            if(i == n - 1)
            {
                result += getInteger(s.charAt(i));
                return result;
            }
            current = getInteger(s.charAt(i));
            next = getInteger(s.charAt(i + 1));
            if(current >= next)
            {
                result += current;
                i++;
            }
            else
            {
                result += next - current;
                i += 2;
            }
        }
        return result;
    }
}

Complexity Analysis of Roman to Integer Leetcode Solution

Time Complexity

Here, we traverse the string once. Since we have an integer limit of less than 4000, the string size will always be a constant value. Therefore, the time complexity is O(1).

Space complexity

O(1), We only use constant memory space.

Approach(Right to Left Pass)

The difference between the right-to-left and left-to-right lies in their implementation. In Right-to-Left pass, we can start from the second last index of the array, storing the integer value of the last character in some variable. We keep the integral value of the last character to the result beforehand. Now, as we move from right to left, we check at every step if the integer value of the current character is less than the last(previous/right) element we have seen. If it is less than the last value, we subtract this value from the result. Otherwise, we add it to our result. This implementation is totally based on the above fact that smaller-valued character before a bigger-valued one means it has to be subtracted from the latter one.

This approach is almost the same in number of operations as the previous approach but is more convenient as we get rid of checking for the last element for every iteration.