Reference: 13. Roman to Integer / 12. Integer to Roman
Difficulty: Easy

## Conversion System

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

• I can be placed before V (5) and X (10) to make IV (4) and IX (9).
• X can be placed before L (50) and C (100) to make XL (40) and XC (90).
• C can be placed before D (500) and M (1000) to make CD (400) and CM (900).

## Roman to Integer

Example:

First, we need a function that receives a character and returns the corresponded value.

The idea is very elegant. Each time we look ahead one element and compare the current element curr with the next element next.

• curr < next: Combination, eg. IX.
• curr >= next: Single Symbol, eg. III.

The way of handling symbols like IX is very clever. We first deduct the value of the first symbol and then add the value of the second symbol. For this example IX, we first deduct I(1) and then add X(5), which turns out to be 4.

Here is the code:

Actually, we can check the index before assigning a value to next. With this check, the code becomes more elegant and succinct.

Time: $O(N)$
Space: $O(1)$

## Integer to Roman

Example:

The idea is to check all possible bases from largest to smallest. For example, we should use M(1000) to reduce 1994 to 994, and then CM(900) and so on.

Time: Depends on the value.
Space: $O(1)$

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.