Integer To Roman Problem

Problem

Roman numerals

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Examples

Example 1:

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58
Output:
 "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Note

This question has a lot of scope of clarification from the interviewer. Please take a moment to think of all the needed clarifications and see the expected response using “See Expected Output” For the purpose of this question, https://projecteuler.net/about=roman_numerals has very detailed explanations.

Solution

If we didn’t had a rule like I can come before V to make 4, this problem was a basic division problem, where we can just greedily divide the number till we get the answer.

Method 1 - Use Array Based Lookup Table

1. We can create two arrays:
   • values array to store the values of Roman numerals in descending order.
   • roman array to store the corresponding Roman numeral strings.
2. Instantiate a StringBuilder to build the resultant Roman numeral string.
3. Iterate through the values Array
   • Check if the Current Value Can Be Subtracted
     • Use a while loop to check if the current integer num is greater than or equal to the current value in the values array.
   • Append the Corresponding Roman Numeral
     • If true, append the corresponding Roman numeral from the roman array to the StringBuilder.
     • Subtract the current value from num.

Code

Java

String intToRoman(int num) {
	int[] values = new int[]{1000,900,500,400,100,90,50,40,10,9,5,4,1};
	String[] roman = new String[]{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
	StringBuilder sb = new StringBuilder();
	for(int i = 0; i < values.length; i++){
		while(num >= values[i]){
			sb.append(roman[i]);
			num -= values[i];
		}
	}
	return sb.toString();
}

Complexity

• ⏰ Time complexity: O(n), where n is length of resulting numeral string
• 🧺 Space complexity: O(k) where k is number of roman numerals supported

Method 2 - Using TreeMap and Recursion

Similar to above code we can use treemap. But treemap will be a bit slower than array based implementation. Here are the steps:

1. Initialize a TreeMap with integer values and their Roman numeral equivalents, including special cases.
2. Define the conversion method intToRoman.
3. Use map.floorKey to find the largest key less than or equal to the input integer.
4. Check if the key is an exact match and return the corresponding Roman numeral if true.
5. Recursively build the Roman numeral string by reducing the input integer and appending corresponding symbols.
6. Combine and test the method.

Code

Java

// java 8 init
final TreeMap<Integer, String> map = new TreeMap<Integer, String>() {{
	put(1000, "M");
	put(900, "CM"); // special case
	put(500, "D");
	put(400, "CD"); // special case
	put(100, "C");
	put(90, "XC"); // special case
	put(50, "L");
	put(40, "XL"); // special case
	put(10, "X");
	put(9, "IX"); // special case
	put(5, "V");
	put(4, "IV"); // special case
	put(1, "I");
}};
public String intToRoman(int A) {
	int l =  map.floorKey(A);
	if (A == l) {
		return map.get(A);
	}
	return map.get(l) + intToRoman(A-l);
}

Complexity

• ⏰ Time complexity: O(nlog k) where n is length of string, and k is number of roman numerals in map
• 🧺 Space complexity: O(k)