LeetCode Explained: 12. Integer to Roman

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

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

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

--

--

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
Wenhe Qi

Wenhe Qi

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