Roman to Integer

Given a Roman numeral between 1 and 3999, return its integer value.

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

Symbols are normally written from largest to smallest and added. Six pairs are subtractive: a smaller symbol placed before a larger one is subtracted from it: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900.

Example

Text

Input:  "XII"      Output: 12
Input:  "MIV"      Output: 1004
Input:  "MCMXCIV"  Output: 1994   (M + CM + XC + IV = 1000 + 900 + 90 + 4)

Brute force: match the subtractive pairs first

Walk the string. At each position, check whether the next two characters form one of the six subtractive pairs. If they do, add the pair's value and skip both. Otherwise add the single symbol's value.

Java

public class Main {
    static int value(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: throw new IllegalArgumentException("not a Roman numeral: " + c);
        }
    }

    static int romanToInt(String s) {
        String[] pairs = {"IV", "IX", "XL", "XC", "CD", "CM"};
        int[] pairValues = {4, 9, 40, 90, 400, 900};
        int total = 0;
        int i = 0;
        while (i < s.length()) {
            int found = -1;
            for (int k = 0; k < pairs.length; k++) {
                if (s.startsWith(pairs[k], i)) {
                    found = k;
                    break;
                }
            }
            if (found >= 0) {
                total += pairValues[found];
                i += 2;
            } else {
                total += value(s.charAt(i));
                i += 1;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        for (String s : new String[] {"XII", "MIV", "MCMXCIV", "III"}) {
            System.out.println(s + " = " + romanToInt(s));
        }
    }
}

Output

XII = 12
MIV = 1004
MCMXCIV = 1994
III = 3

Time: O(n), with up to six pair comparisons per position. Space: O(1).

Optimal: compare each symbol with the next

The pair table is not needed. A symbol is subtracted exactly when the symbol after it is larger; otherwise it is added. This rule covers all six pairs at once.

Walkthrough with "MCMXCIV":

symbol	value	next	action	total
M	1000	C (100)	add	1000
C	100	M (1000)	subtract	900
M	1000	X (10)	add	1900
X	10	C (100)	subtract	1890
C	100	I (1)	add	1990
I	1	V (5)	subtract	1989
V	5		add	1994

Java

public class Main {
    static int value(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: throw new IllegalArgumentException("not a Roman numeral: " + c);
        }
    }

    static int romanToInt(String s) {
        int total = 0;
        for (int i = 0; i < s.length(); i++) {
            int v = value(s.charAt(i));
            if (i + 1 < s.length() && value(s.charAt(i + 1)) > v) {
                total -= v;
            } else {
                total += v;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        for (String s : new String[] {"XII", "MIV", "MCMXCIV", "III"}) {
            System.out.println(s + " = " + romanToInt(s));
        }
    }
}

Output

XII = 12
MIV = 1004
MCMXCIV = 1994
III = 3

Time: O(n). Space: O(1): the next symbol is looked up directly with value(s.charAt(i + 1)), so no list of values is built.

Edge cases

Single symbol: "M" is 1000; there is no next symbol, so it is added.
Invalid input: this version throws IllegalArgumentException on unknown characters. Return OptionalInt instead if the input is not guaranteed to be valid.
Non-canonical numerals such as "IIII" or "IM" are still summed by the same rule. Rejecting them needs extra validation.