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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s