Xiaokang's Study Notes

Roman Integer Conversion

by | Jan 18, 2017 | Algorithm & Data Structure | 0 comments

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