Convert Integer to Roman in Java

Ashish Lahoti

Last Modified: September 15, 2020

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:

1	2	3	4	5	6	7	8	9
I	II	III	IV	V	VI	VII	VIII	IX

10	20	30	40	50	60	70	80	90
X	XX	XXX	XL	L	LX	LXX	LXXX	XC

100	200	300	400	500	600	700	800	900
C	CC	CCC	CD	D	DC	DCC	DCCC	CM

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:

We will append that roman numeral to the new initialized string
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);
}