# 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 preturn 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.