Integer to Roman

Step 1: Treat the subtractive forms as symbols too

The awkward cases, 4 and 9 in each place, become easy if CM, CD, XC, XL, IX and IV are simply extra symbols. That gives 13 symbols in all, from M = 1000 down to I = 1.

Step 2: Always take the largest symbol that fits

Go through the 13 symbols from largest to smallest. While the number is at least the symbol's value, write the symbol and subtract its value.

Step 3: Why greedy is right here

With the subtractive pairs in the table, every number has exactly one valid Roman form, and it is the one that uses the largest symbols first. For 1994, taking M leaves 994; the largest symbol that fits 994 is CM, not D, which gives the correct "MCM...".

num = 1994.

Two parallel arrays hold the 13 values and their symbols, largest first.

public class IntegerToRoman {

    private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private static final String[] SYMBOLS =
            {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public static String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < VALUES.length; i++) {
            while (num >= VALUES[i]) {        // take the largest symbol that still fits
                sb.append(SYMBOLS[i]);
                num -= VALUES[i];
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(intToRoman(3749));   // MMMDCCXLIX
        System.out.println(intToRoman(58));     // LVIII
        System.out.println(intToRoman(1994));   // MCMXCIV
    }
}

The original implementation, IntegerToRoman.java, is on GitHub.

• Time: O(1): the input is at most 3999, so the output has at most 15 symbols.
• Space: O(1).

The reverse conversion is Roman to Integer.