Roman to Integer

Roman numerals are represented by seven different symbols: IVXLCD 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.

Given that the representation for 3 is III, it could seem natural that the representation for 15 is VVV, because that would be  5+5+5. However, it’s actually XV, which is 10+5. How are you even supposed to know which is correct? The trick is to use the “biggest” symbols you can. Because X is bigger than V, we should use an X first and then make up the remainder with a single V, giving XV.

A few more examples

If you’re not very familiar with Roman Numerals, work through these examples and then have another go at writing your own algorithm before reading the rest of this solution article.

What is CXVII as an integer?

Recall that C = 100X = 10V = 5, and I = 1. Because the symbols are ordered from most significant to least, we can simply add the symbols, i.e. C + X + V + I + I = 100 + 10 + 5 + 1 + 1 = 117.

What is DXCI as an integer?

Recall that D = 500.

Now, notice that this time the symbols are not ordered from most significant to least—the X and C are out of numeric order. Because of this, we subtract the value of X (10) from the value of C (100) to get 90.

So, going from left to right, we have D + (C - X) + I = 500 + 90 + 1 = 591.

What is CMXCIV as an integer?

Recall that M = 1000.

The symbols barely look sorted at all here—from left-to-right we have 100, 1000, 10, 100, 1, 5. Do not panic though, we just need to look for each occurrence of a smaller symbols preceding a bigger symbol. The first, third, and fifth symbols are all smaller than their next symbol. Therefore they are all going to be subtracted from their next.

  • The first two symbols are CM. This is M - C = 1000 - 100 = 900
  • The second two symbols are XC. This is C - X = 100 - 10 = 90.
  • The final two symbols are IV. This is V - I = 5 - 1 = 4.

Like we did above, we add these together. (M - C) + (C - X) + (V - I) = 900 + 90 + 4 = 994.


Approach: Left-to-Right Pass

Let’s hard-code a mapping with the value of each symbol so that we can easily look them up.

private Map<Character, Integer> romanMap = new HashMap<>(){{
        put('I',1);
        put('V',5);
        put('X',10);
        put('L',50);
        put('C',100);
        put('D',500);
        put('M',1000);
}};

Now, recall that each symbol adds its own value, except for when a smaller valued symbol is before a larger valued symbol. In those cases, instead of adding both symbols to the total, we need to subtract the large from the small, adding that instead. Therefore, the simplest algorithm is to use a pointer to scan through the string, at each step deciding whether to add the current symbol and go forward 1 place, or add the difference of the next 2 symbols and go forward 2 places. Here is this algorithm in pseudocode.

total = 0
i = 0
while i < s.length:
    if at least 2 symbols remaining AND value of s[i] < value of s[i + 1]:
        total = total + (value of s[i + 1]) - (value of s[i])  
        i = i + 2
    else:
        total = total + (value of s[i])
        i = i + 1
return total

Here is an animation of the above algorithm. Recall that the input is always valid. This means that we don’t need to worry about being given inputs such as ICD.

Implementation

class Solution {
    private Map<Character, Integer> romanMap = new HashMap<>(){{
        put('I',1);
        put('V',5);
        put('X',10);
        put('L',50);
        put('C',100);
        put('D',500);
        put('M',1000);
    }};

    public int romanToInt(String s) {

        int result = 0;
        if( s == null || s.isEmpty()){
            return result;
        }
        int  i = 0;
        int len = s.length();
        while( i < len){
            int current = romanMap.get(s.charAt(i));
            int next = 0;
            if( i != (len-1)){
                next = romanMap.get(s.charAt(i + 1));
            }
            if(current >= next){
                result = result + current;
                i++;
            }else{
                result = result + (next - current);
                i += 2;
            }
        }
        return result;
    }
}

Categories: Map

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s