Programming with Passion Algorithms, Mobile Development, Robotics

Sunday, May 28, 2017

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);
}

No comments:

Post a Comment