Roman Numeral to Integer

medium Number Problems

Problem

Read a valid Roman numeral (value from 1 to 3999) and print its integer value. A smaller letter in front of a larger letter is subtracted (IV = 4). Otherwise the values are added.

Constraints

  • Valid Roman numeral, 1 <= value <= 3999

Examples

Input

MCMXCIV

Output

1994

Solutions

Best approachTime O(n)Space O(1)

We read the letters one by one. If the next letter has a larger value, the current letter is a 'subtract' letter. This one rule handles IV, IX, XL, XC, CD and CM.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Convert a Roman numeral to an integer.
 * Input   : One valid Roman numeral.
 * Output  : The integer value.
 * Approach: Subtract a value when a larger value follows it.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives one Roman letter and returns its value.
    static int valueOf(char letter) {
        switch (letter) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000; // the letter M
        }
    }

    public static void main(String[] args) {
        String text = new Scanner(System.in).next();

        // Step 1: The total starts at 0.
        int total = 0;

        // Step 2: Go through the letters from left to right.
        for (int index = 0; index < text.length(); index++) {
            int current = valueOf(text.charAt(index));

            // Step 3: If a larger letter follows, subtract this value. Example: in IV, the letter I is subtracted.
            if (index + 1 < text.length() && current < valueOf(text.charAt(index + 1))) {
                total = total - current;
            } else {
                // Step 4: Otherwise add this value.
                total = total + current;
            }
        }

        // Step 5: Print the total.
        System.out.println(total);
    }
}
Hints (1)
  1. Compare each letter with the next letter.