Convert Integer to Roman in Java Convert Integer to Roman in Java

Page content

Problem: Given an Integer input, convert it to a Roman numeral. Input is within the range from 1 to 3999.

Source Code: IntegerToRoman.java

Also read Convert Roman to Integer in Java

About Roman Numerals

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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

These symbols can be combined like this to create numbers:

123456789
IIIIIIIVVVIVIIVIIIIX
102030405060708090
XXXXXXXLLLXLXXLXXXXC
100200300400500600700800900
CCCCCCCDDDCDCCDCCCCM

Things to note in roman numbers:

  • When a symbol appears after a larger (or equal) symbol it is added
    Example: VI = V + I = 5 + 1 = 6
    Example: LXX = L + X + X = 50 + 10 + 10 = 70
  • But if the symbol appears before a larger symbol it is subtracted
    Example: IV = V − I = 5 − 1 = 4
    Example: IX = X − I = 10 − 1 = 9
  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Approach

Naive Approach

In this approach we’ll start checking with highest possible number which can be converted into Roman numerals i.e. 1000 = M. If possible to convert then:

  1. We will append that roman numeral to the new initialized string
  2. We will subtract the highest number from the given number

We’ll follow this checking approach till the smallest possible number which can be converted into Roman numerals i.e 1 = I

public static String integerToRoman1(int number) {
	StringBuilder s = new StringBuilder();
	while (number >= 1000) {
		s.append("M");
		number -= 1000;
	}
	while (number >= 900) {
		s.append("CM");
		number -= 900;
	}
	while (number >= 500) {
		s.append("D");
		number -= 500;
	}
	while (number >= 400) {
		s.append("CD");
		number -= 400;
	}
	while (number >= 100) {
		s.append("C");
		number -= 100;
	}
	while (number >= 90) {
		s.append("XC");
		number -= 90;
	}
	while (number >= 50) {
		s.append("L");
		number -= 50;
	}
	while (number >= 40) {
		s.append("XL");
		number -= 40;
	}
	while (number >= 10) {
		s.append("X");
		number -= 10;
	}
	while (number >= 9) {
		s.append("IX");
		number -= 9;
	}
	while (number >= 5) {
		s.append("V");
		number -= 5;
	}
	while (number >= 4) {
		s.append("IV");
		number -= 4;
	}
	while (number >= 1) {
		s.append("I");
		number -= 1;
	}
	return s.toString();
}


Improvement using Arrays

We can further enhance our code to remove the repetition of while code. We’ll save largest to smallest numbers and their roman numerals in Arrays [].

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

public static final String integerToRoman2(int number) {

	StringBuilder s = new StringBuilder();

	for (int i = 0; i < values.length; i++) {
		while (number >= values[i]) {
			number -= values[i];
			s.append(romanLiterals[i]);
		}
	}
	return s.toString();
}


Dynamic (Recursive) Approach using Arrays

Let’s try our hands on dynamic programming and solve the same problem using recursive approach.

Note that we have created a private method getFloorIndex which gives us the index of greatest value less than or equal to the given number.

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

public static final String integerToRoman3(int number) {

	int i = getFloorIndex(number);
	if (number == values[i]) {
		return romanLiterals[i];
	}

	return romanLiterals[i] + integerToRoman3(number - values[i]);
}

private static int getFloorIndex(int number) {
	for (int i = 0; i < values.length; i++) {
		while (number >= values[i]) {
			return i;
		}
	}
	return -1;
}


Dynamic (Recursive) Approach using TreeMap

Let’s make our code more concise by saving largest to smallest number and their roman numerals in TreeMap instead of Arrays [].

Note that TreeMap has a built-in floorKey method which gives the greatest key less than or equal to the given number.

// Approach 4
private static final TreeMap<Integer, String> treemap = new TreeMap<Integer, String>();
static {
	treemap.put(1000, "M");
	treemap.put(900, "CM");
	treemap.put(500, "D");
	treemap.put(400, "CD");
	treemap.put(100, "C");
	treemap.put(90, "XC");
	treemap.put(50, "L");
	treemap.put(40, "XL");
	treemap.put(10, "X");
	treemap.put(9, "IX");
	treemap.put(5, "V");
	treemap.put(4, "IV");
	treemap.put(1, "I");

}

public static final String integerToRoman5(int number) {
	int l = treemap.floorKey(number);
	if (number == l) {
		return treemap.get(number);
	}
	return treemap.get(l) + integerToRoman5(number - l);
}