# Roman to Integer

Roman numerals are represented by seven different symbols: `I``V``X``L``C``D` 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 = 100``X = 10``V = 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
``````

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: