11. Integer to Roman

Problem

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.

Problem description

Given an integer, the task is to convert it to a Roman numeral. Roman numerals are a numeral system used in ancient Rome and are based on seven symbols: I, V, X, L, C, D, and M. Each symbol represents a specific value in the decimal system. The symbols must be written in descending order of value, from left to right. However, there are instances where subtraction is used. For example, the number four is written as IV, which is I before V (5), making 4.

Solution

The Roman numeral system is based on the use of seven symbols to represent numbers: I, V, X, L, C, D, and M. To convert a decimal number to a Roman numeral, we need to understand the rules and values of these symbols. The most important rule is that symbols must be placed in descending order of value, from left to right. The most efficient way to do this is to use a greedy approach, where we subtract the largest possible symbol from the integer until it becomes 0.

Algorithm

1. Create four arrays “thousands”, “hundreds”, “tens” and “ones” to store the Roman numerals.
2. Initialize the arrays with the values of Roman numerals from 1 to 9, with empty string “” representing 0.
3. Calculate the thousands place value of the given integer by dividing the integer by 1000 and storing the result in a variable.
4. Calculate the hundreds place value of the given integer by dividing the integer by 100 and storing the remainder in a variable.
5. Calculate the tens place value of the given integer by dividing the integer by 10 and storing the remainder in a variable.
6. Calculate the ones place value of the given integer by taking the remainder after dividing the integer by 10.
7. Concatenate the values stored in the arrays at the respective index of the calculated thousands, hundreds, tens and ones place values.
8. Return the result as a string.

C#

class Program
    {
        static string IntToRoman(int num)
        {
            string[] thousands = { "", "M", "MM", "MMM" };
            string[] hundreds = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
            string[] tens = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
            string[] ones = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
            return thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
        }
    }

Java

public class IntegerToRoman {

    public static String intToRoman(int num) {
        String[] thousands = { "", "M", "MM", "MMM" };
        String[] hundreds = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
        String[] tens = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
        String[] ones = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
        return thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
    }
}

C++

#include <iostream>
#include <string>


public:
    string intToRoman(int num) {
        string thousands[] = {"", "M", "MM", "MMM"};
        string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return thousands[num / 1000] + hundreds[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
    }

JavaScript

function intToRoman(num) {
  const thousands = [ "", "M", "MM", "MMM" ];
  const hundreds = [ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" ];
  const tens = [ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" ];
  const ones = [ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" ];
  return thousands[Math.floor(num / 1000)] + hundreds[Math.floor((num % 1000) / 100)] + tens[Math.floor((num % 100) / 10)] + ones[num % 10];
}

Python

def intToRoman(num):
    thousands = [ "", "M", "MM", "MMM" ]
    hundreds = [ "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" ]
    tens = [ "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" ]
    ones = [ "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" ]
    return thousands[num // 1000] + hundreds[(num % 1000) // 100] + tens[(num % 100) // 10] + ones[num % 10]

Time and space complexity:

The time complexity of this solution is O(1), as the number of symbols in the SYMBOLS array is constant and does not depend on the input.

The space complexity is also O(1), as the size of the output result string is proportional to the number of symbols used, which is limited by the range of the input integer.

Conclusion

In this article, we discussed a solution to convert a decimal integer to a Roman numeral. The solution is efficient, with a constant time and space complexity. By following the algorithm outlined above, you can easily implement this conversion in your own projects. Additionally, the greedy approach used in this solution ensures that the final Roman numeral is optimized and uses the smallest number of symbols possible.