## 13 – Roman to Integer

### Problem statement

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.

**Exmpale 5**:

Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90, and IV = 4.

Taken from:

leetcode

### Approach and Analysis

#### Approach #1

Setting aside the one big exception for the time being, the basic

mechanism for turning our roman numeral into an integer is pretty

straightforward. We can iterate through each character of the string,

mapping each one to its equivalent numeric value as we go. Finally,

we can add these to a variable that tracks our total sum. After having

passed through all of the characters, we can return this sum as the

output of our program.

To address the case where the next character is bigger than the current

one (and we should subtract it instead of adding it to `sum`

), we can look

ahead to the next value and perform the correct piece of logic accordingly.

#### Complexity

The complexity for this approach is as follows:

- O(n) time complexity
- O(1) space complexity

– No additional space is needed

### Rust solution (Approach #1)

fn parse(c: char) -> i32 { match c { 'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000, _ => 0 } } impl Solution { pub fn roman_to_int(s: String) -> i32 { // The vector of characters expects to be indexed // by a value of type "usize" let mut i: usize = 0; let mut sum: i32 = 0; let char_vec: Vec<char> = s.chars().collect(); let vec_len = char_vec.len(); while (i < vec_len) { let curr: i32 = parse(char_vec[i]); // Look ahead to the next element if possible if (i + 1) < vec_len { let next: i32 = parse(char_vec[i+1]); if (next > curr) { sum -= 2 * curr; } } sum += curr; i += 1; } sum } }

One quirk of this solution’s implementation is that I’ve elected

to subtract double the current value in the instance where subtraction

is used.

Our logic in this scenario is the following:

- If next exists and next > curr, we subtract 2 * curr from sum
- For each element, add curr

For scenarios where `1`

and `2`

apply, the net result consists of

subtracting curr from sum.

This saves us from needing implement logic like so:

- If next exists and next > curr, subtract curr from sum
- If next exists and next < curr, add curr to sum
- If next does not exist, add curr to sum

Notice the duplicate logic in `2`

and `3`

### Bonus solution (Using iterators)

fn parse(c: char) -> i32 { match c { 'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000, _ => 0 } } impl Solution { pub fn roman_to_int(s: String) -> i32 { let mut iter = s.chars().map(|c| parse(c)).peekable(); let mut acc = 0; loop { match iter.next() { Some(x) => { match iter.peek() { // Peek returns a reference to // the next element Some(&p) => { if p > x { acc -= 2*x } }, None => {} }; acc += x; }, None => break } } acc } }

This solution was an exercise in using only iterators to answer

the question. Accomplishing this requires that we transform the

iterator into one which has a “peek” function that we can use

to look at the next value without iterating over it.

While interesting as a proof of concept, in practice, this

solution has one glaring issue. Because we have to handle

“Options” that are returned from the iterator methods `.next()`

and `.peek()`

, the code has many levels of nesting that make

it hard to read.

Additionally, according to leetcode, this solution takes about

4 times as long to run (0 ms vs. 4 ms).

### What I learned by solving this problem

My first solution to this problem, being straightforward, didn’t

teach me anything new about rust. The part of the problem that

proved most challenging was the logic surrounding the “lookahead”

and ensuring that I didn’t attempt to index the array at a position

that doesn’t exist.

#### Working with Iterators

By finagling my way to a solution involving iterators, I learned

that there are some scenarios in which it simply doesn’t make

sense to use this paradigm.

While rust’s `peekable`

struct did make an iterator solution

possible, simply using loops was much simpler.

As a point of interest, somebody did post an incredibly elegant

solution using iterators: [iterator solution (https://leetcode.com/problems/roman-to-integer/discuss/374718/Rust-pattern-matching-without-extra-allocation).

This solution took advantage of a point in the problem description

that I ignored: “Roman numerals are usually writte largest to smallest

from left to right”. I learned from this that reading deeper into

the question may uncover assumptions that allow us to achieve the

most elegant solution.