Roman To Integer

Today we will learn about a famous interview question Roman Numerals to Integer. The question is simple but still requires one of those “Aha” moments to solve.

Problem Statement

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Example :

Input : “XIV”
Output : 14

Input : “XX”
Output : 20

Now I know most of you are familiar with Roman Numerals. But we are still going to go over them briefly. Also keep in mind we will base all of our assumptions for the input range 1-3999 as given in the question.

Roman Numerals

Roman Numerals are numbers formed by combining symbols. These are based on seven symbols. Other symbols are produces by combining two or more of the basic symbols.

Symbol	Value
I	1
IV	4
V	5
IX	9
X	10
XL	40
L	50
XC	90
C	100
CD	400
D	500
CM	900
M	1000

So Two assumptions can be derived from our knowledge of Roman Numerals –

1. The symbol at i is always greater than all the symbols following it.
2. Two symbols can be combined to formed one symbol.

Algorithm

sum := 0
i := 0

// Iterate over each symbol in Roman string
Repeat while i < len(string) do:
	current_symbol := symbol(i)

    // If the symbol is smaller than the succeeding symbol
	// Then combine both symbols as one
	if value(symbol(i)) < value(symbol(i+1)) do:
		current_symbol := symbol(i) + symbol(i+1)
		increment i
	end

    // Add the corresponding symbol value from table to sum
	sum := sum + value(current_symbol)
	increment i
end

 

Testing

Now that we have worked out the algorithm, Let’s test it before moving on to the coding part.

input := XXIV
output := 24

That’s what we wanted. So the Algorithm works.

Implementation in C++ is available at GitHub