Integer to Roman
Introduction
Seven different symbols represent Roman numerals with the following values:
Symbol | Value |
---|---|
I | 1 |
V | 5 |
X | 10 |
L | 50 |
C | 100 |
D | 500 |
M | 1000 |
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
- If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
-
If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol,
for example, 4 is 1 (
) less than 5 (I
):V
and 9 is 1 (IV
) less than 10 (I
):X
. Only the following subtractive forms are used: 4 (IX
), 9 (IV
), 40 (IX
), 90 (XL
), 400 (XC
) and 900 (CD
).CM
-
Only powers of 10 (
,I
,X
,C
) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (M
), 50 (V
), or 500 (L
) multiple times. If you need to append a symbol 4 times use the subtractive form.D
Given an integer, convert it to a Roman numeral.
Example 1
Output: "MMMDCCXLIX"
Explanation: 3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
700 = DCC as 500 (D) + 100 (C) + 100 (C)
40 = XL as 10 (X) less of 50 (L)
9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
Example 2
Output: "LVIII"
Explanation: 50 = L
8 = VIII
Example 3
Output: "MCMXCIV"
Explanation: 1000 = M
900 = CM
90 = XC
4 = IV
Constraints:
1 <= num <= 3999
Add extra special cases into Roman Symbol table
As per the problem statement, there are six special cases when converting integer to roman representation, so in this approach, we will add the extra entries into roman to integer table and then divide the input number possible with highest number to lowest in the integer int the roman to integer mapping, once divided then continue the process with the remainder.
After updating the roman to integer, mapping will look like this
Symbol | I | IV | V | IX | X | XL | L | XC | C | CD | D | CM | M |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Value | 1 | 4 | 5 | 9 | 10 | 40 | 50 | 90 | 100 | 400 | 500 | 900 | 1000 |
Now, let's apply above mapping to a an example num = 3749
-
First, we will try to divide using the highest number in roman to integer table, which is
and we can divide input number 3 times so we will add1000
to the result, and update theMMM
with remainder, which isnum
749
-
Next biggest number in roman to integer table is
, and we cannot divide900
using this.749
-
Next biggest number in roman to integer table is
, and we can divide500
one time, so add749
to the result, so the result now becomesD
and remainder will becomeMMMD
.249
-
Next biggest number in roman to integer table is
, and we cannot divide400
with this.249
-
Next biggest number in roman to integer table is
, and we can divide100
two times, so add249
to the result, so the result now becomesCC
and remainder will becomeMMMDCC
.49
-
Next biggest number in roman to integer table is
, and we cannot divide90
with this.49
-
Next biggest number in roman to integer table is
, and we cannot divide50
with this.49
-
Next biggest number in roman to integer table is
, and we can divide40
one time, so add49
to the result, so the result now becomesXL
and remainder will becomeMMMDCCXL
.9
-
Next biggest number in roman to integer table is
, and we cannot divide10
with this.9
-
Next biggest number in roman to integer table is
, and we can divide9
one time, so add9
to the result, so the result now becomesIX
and remainder will becomeMMMDCCXLIX
.0
import java.util.AbstractMap;
import java.util.Map;
public class IntegerToRoman {
static final String[] romanOrder = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
static final int[] intOrder = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
static String intToRoman(int num) {
StringBuilder sb = new StringBuilder();
for(int i= intOrder.length-1; i>=0; i--){
int div = num / intOrder[i];
if(div>0) {
sb.append(romanOrder[i].repeat(div));
num = num % intOrder[i];
}
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(intToRoman(3749));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(1) time since we are only iterating through roman to integer mapping array, which is constant.
Space complexity: O(1).
Above implementations source code can be found at