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.

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 representationset res be empty stringfor 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.

A lifelong learner who has enthusiasm for sharing knowledge; a developer who loves bringing ideas to life.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store