Integer to Roman

Tags:

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:

Given an integer, convert it to a Roman numeral.

Example 1
Input: num = 3749
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
Input: num = 58
Output: "LVIII"
Explanation: 50 = L
8 = VIII
Example 3
Input: num = 1994
Output: "MCMXCIV"
Explanation: 1000 = M
900 = CM
90 = XC
4 = IV
Constraints:

Contents

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 1000 and we can divide input number 3 times so we will add MMM to the result, and update the num with remainder, which is 749
  • Next biggest number in roman to integer table is 900, and we cannot divide 749 using this.
  • Next biggest number in roman to integer table is 500, and we can divide 749 one time, so add D to the result, so the result now becomes MMMD and remainder will become 249.
  • Next biggest number in roman to integer table is 400, and we cannot divide 249 with this.
  • Next biggest number in roman to integer table is 100, and we can divide 249 two times, so add CC to the result, so the result now becomes MMMDCC and remainder will become 49.
  • Next biggest number in roman to integer table is 90, and we cannot divide 49 with this.
  • Next biggest number in roman to integer table is 50, and we cannot divide 49 with this.
  • Next biggest number in roman to integer table is 40, and we can divide 49 one time, so add XL to the result, so the result now becomes MMMDCCXL and remainder will become 9.
  • Next biggest number in roman to integer table is 10, and we cannot divide 9 with this.
  • Next biggest number in roman to integer table is 9, and we can divide 9 one time, so add IX to the result, so the result now becomes MMMDCCXLIX and remainder will become 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 GitHub link for Java code