LeetCode Explained: 12. Integer to Roman

In this question, we are asked to write a routine to convert an Arabic integer number (I’ll use number to save some typing) into Roman numerals.

To better understand how a number can be represented in Roman numerals, I created below chart:

From above chart, we can observe below patterns:

1. unit of each place is represented with a distinct symbol, e.g. ‘I’ for ones place, ‘X’ for tens place, ‘C’ for hundreds place, etc.
2. number 5 in each place is also represented with a distinct symbol, e.g. 5 in ones place is ‘V’, 5 in tens place is ‘L’, etc.
3. for numbers between 1 to 3 in a place, the Roman representation is the unit of that place repeated number times, e.g. 3 on hundreds place, which is 300, is ‘C’ repeated 3 times.
4. for number 4 in a place, the Roman representation is the unit of that place appended with number 5 of that place, e.g. 4 in ones place is ‘I’ appended with ‘V’, which is “IV”. You can also think of it as 5 minus 1.
5. for numbers between 5 and 8, the Roman representation is the number 5 of that place followed by the unit of that place repeated number-5 times, e.g. 7 on hundreds place, 700, is ‘D’ appended with ‘C’ repeated twice, so it’s “DCC”. You can also think of it as 500 plus 200.
6. for number 9 in a place, the Roman representation is the unit of that place appended with the unit of the next place, e.g, 9 in tens place is ‘X’ appended with ‘C’, which is “XC”.

Now let’s think of a number in [1, 3999] and convert it to Roman numerals.

Let’s say the number is 2754.

Firstly, we examine thousands place: 2 should be ‘M’ repeated twice, which is “MM”.

Secondly, we examine the hundreds place: 7 should be ‘D’ followed by two ‘C’, which is “DCC”.

Thirdly, we examine the tens place: 5 should be ‘L’ followed by zero ‘X’, which is just “L”.

Lastly, we examine the ones place: 4 should be ‘I’ followed by ‘V’, which is “IV”.

Now concatenate the results of each place in the order we examine them, finally we get “MMDCCLIV” as the Roman representation of 2754.

Approach 0: Brute Force

To be honest, I can’t think of a name other than brute force at this moment. Please feel free to let me know if you have other naming suggestions.

let res be the result Roman representation
set res be empty string
for each place from high to low
    let n be the number in that place
    let u be the unit symbol of this place
    let m be the symbol of number 5 of this place
    let p be the unit symbol of next place
    if n < 4:
        res += u repeated n times
    else if n == 4:
        res += u followed by m
    else if n < 9:
        res += m followed by u repeated (n - 5) times
    else:
        res += u followed by p
return res

Here is a Java implementation of above algorithm:

Time complexity: O(n) where n is the number of digits that makes up the input number.

Space complexity: O(1) if the returned result is not counted. We only used constant memory to create a matrix to store unit symbol and number 5’s symbol of each place.

Follow Up

For this question the input number is bounded between 1 and 3999. What if there is no such restriction? Say the input can be in [1, infinity).

In this case we still have to be given all the unit symbols of each place and also number 5’s symbols. While instead of looping through the number from the most significant digit, we start from the opposite direction, calculate the Roman representation of each place and insert it to the start of the previous result string and finally return the result.