LeetCode (Algorithms#12) ‒ Integer to Roman

Problem

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

Solution

The problem is pretty straightforward once you realize all cases of roman numerals. The cases can be split up into $n < 4$, $4 \leq n < 5$, $5 \leq n < 9$, and $n \geq 9$, and are repeated for 10s, 100s, etc. In the code below, we simply iterate over each digit of the integer, and append characters according to the case.

Time complexity: $O(n)$
Space complexity: $O(n)$
Runtime: 97 ms (69.14%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public String intToRoman(int num) { StringBuilder sb = new StringBuilder(); int n = num/1000; if (n > 0) appendN(sb,'M',n); num%=1000; if (num>=400 && num<500) sb.append("CD"); else if (num<400) appendN(sb,'C',num/100); else if (num<900) appendN(sb.append("D"),'C',(num-500)/100); else sb.append("CM"); num%=100; if (num>=40 && num<50) sb.append("XL"); else if (num<40) appendN(sb,'X',num/10); else if (num<90) appendN(sb.append("L"),'X',(num-50)/10); else sb.append("XC"); num%=10; if (num==4) sb.append("IV"); else if (num<4) appendN(sb,'I',num); else if (num<9) appendN(sb.append("V"),'I',num-5); else sb.append("IX"); return sb.toString(); } void appendN(StringBuilder sb, char c, int n) { for (int i=0; i<n; i++) sb.append(c); }