Roman Integer Conversion

Roman to Integer

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

To solve this problem, let’s first take a look at all roman numbers.

Roman Number

Roman number has the following basic symbols:

 
 1: I
 5: V
 10: X
 50: L
 100: C
 500: D
 1000: M

Then let’s see how roman number is composed:

  • Numbers are formed by combining symbols and adding values
  • Symbols have fixed value, no relative number.
  • Symbols are placed from left to right, starting with the largest
  • Subtractive notation is used to avoid four character being repeated: place a smaller symbols to the left.
  • Subtractive notation notation is limited: “““

Subtractive notation is one of the key rules of forming roman integer, here are some example of roman number:

  
  4: IV
  9: IX
  40:XL
  90:XC
  400: CD
  900: CM
  3999: MMMCMXCIX

So to convert a roman number to an integer, we need to determine whether it is additive or subtractive.

In subtractive notation, we have the following observation:

  • The symbol that is relatively smaller represents negative value
  • The symbol that is relatively larger represents positive value
  • Negative symbol is placed on the left.

And we have the following algorithm:

    
    rightMax = 0 
    Scan by char from right to left:
        value = map(ch)
        if rightMax <= value:
            value should be added to total
            rightMax <- value
        else
            value should be subtract from total
    return total

The following code implements the algorithm described:

    
    public class solution {
    Map<Character, Integer> map = new HashMap<Character, Integer> ();
    public Solution() {
       map.put('I', 1);
       map.put('V', 5);
       map.put('X', 10);
       map.put('L', 50);
       map.put('C', 100);
       map.put('D', 500);
       map.put('M', 1000);
    }

    public int romanToInt(String s) {
        int rightMax = 0;
        int ret = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int value = map.get(s.charAt(i));
            if (value >= rightMax) {
                rightMax = value;
                ret += value;
            } else {
                ret -= value;
            }
        }

        return ret;
    }

} 

Integer to roman problem

As we know, roman number are composed from right to left with absolute number, so we only need to find out all possible symbols of roman number to get the integer value.

The algorithm is simple:

    
     intToRoman(v):
        ret = ""
        while (v != 0) {
            if (v > last_roman) {
                ret += last_roman
                v %= last_roman
            } else {
                last_roman = next roman
            }
        }
        return ret

The following code implements the algorithm above:


public String intToRoman(int num) {
   String[] roms = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
   int[] ints = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
   StringBuilder result = new StringBuilder();

   for (int i = 0; i < ints.length; i++) {
     while (num >= ints[i]) {
            result.append(roms[i]);
           num -= ints[i];
           }
   }
   return result.toString();
}

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