Algorithms – Integer to Roman

We did a post which shows how to convert Roman to Integer here, in this post we are going to walk through converting Integer to Roman. Enjoy this tutorial!

Question

Given an integer, convert it to a roman numeral.

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.

Description

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

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• 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.

Given an integer, convert it to a roman numeral.

Steps

Step 1: Initialize the INTEGERS and ROMANS arrays

The INTEGERS array contains a list of integers in decreasing order, ranging from 1000 to 1. The ROMANS array contains the corresponding Roman numerals for each integer in the INTEGERS array.

Step 2: Define the base case

The base case is when num is less than 1. In this case, the method immediately returns an empty string.

Step 3: Iterate through the INTEGERS array

The method iterates through the INTEGERS array using a for loop. The loop starts at index 0 and runs until the end of the array.

Step 4: Check if num is greater than or equal to the current INTEGERS element

Inside the loop, the method checks whether num is greater than or equal to the current element in the INTEGERS array. If it is, the method proceeds to the next step.

Step 5: Return the Roman numeral for the current INTEGERS element

If num is greater than or equal to the current INTEGERS element, the method returns the corresponding Roman numeral from the ROMANS array. The Roman numeral is returned as a string.

Step 6: Recursively call intToRoman with the remainder

After returning the Roman numeral for the current INTEGERS element, the method recursively calls itself with the remainder of num minus the current INTEGERS element

Solution

Java Implementation

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

    public String intToRoman(int num){
        for (int i = 0; i < INTEGERS.length; i++){
            if (num >= INTEGERS[i]){
                return ROMANS[i] + intToRoman(num - INTEGERS[i]);
            }
        }
        return "";
    }

Conclusion

This algorithm is an example of a recursive algorithm. Recursive algorithms are a type of algorithm that solve a problem by breaking it down into smaller sub-problems, and then solving those sub-problems using the same algorithm. The algorithm continues to call itself repeatedly until it reaches a base case, which is a problem that can be solved directly without calling the algorithm again.

In the case of the Roman numeral converter, the algorithm starts by checking if the input number is less than 1, which is the base case. If the input number is greater than or equal to 1, the algorithm calls itself with the input number reduced by the largest integer that divides the input number without leaving a remainder (i.e. the largest integer that can be subtracted from the input number to get a result that is a multiple of 10). This process continues until the input number is reduced to less than 1, at which point the algorithm returns the Roman numeral for the remaining number.

Recursive algorithms are often used to solve problems that have a recursive structure, meaning that the problem can be broken down into smaller sub-problems that are similar to the original problem. They are particularly useful for solving problems that have a clear base case, and for solving problems that can be solved by breaking them down into smaller pieces and solving each piece separately.

Check out my other article or Algorithm – Reverse words in a string here

Our Facebook page is here. You can also find our Youtube channel here.