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

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

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 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 Pseudocode**

```
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
}
```

Helper function integerValues(char 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
}
```

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 Pseudocode**

```
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 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).

- 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?

- 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!**

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.