Leetcode: Integer to Roman

Given an integer, convert it to a roman numeral.

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

Understand the problem:
The crux of the problem is obviously to understand the roman numeral.
According to wiki, The numbers 1 to 10 can be expressed in Roman numerals as follows:

I, II, III, IV, V, VI, VII, VIII, IX, X.

Reading Roman numerals[edit]

MMXIV

"2014" as a Roman numeral

Roman Numerals, as used today, are based on seven symbols:^[1]

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1,000

Numbers are formed by combining symbols and adding the values. So II is two ones, i.e. 2, and XIII is a ten and three ones, i.e. 13. There is no zero in this system, so 207, for example, is CCVII, using the symbols for two hundreds, a five and two ones. 1066 is MLXVI, one thousand, fifty and ten, a five and a one.

Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases,^[2] to avoid four characters being repeated in succession (such as IIII or XXXX) these can be reduced using subtractive notation as follows:^[3][4]

• the numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX) respectively
• X can be placed before L and C to make 40 (XL) and 90 (XC) respectively
• C can be placed before D and M to make 400 (CD) and 900 (CM) according to the same pattern^[5]

An example using the above rules would be 1904: this is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 4 (four units). To write the Roman numeral, each of the non-zero digits should be treated separately. Thus 1,000 = M, 900 = CM, and 4 = IV. Therefore, 1904 is MCMIV.

Below are some examples of the modern use of Roman Numerals.

• 1954 as MCMLIV (Trailer for the movie The Last Time I Saw Paris)^[6]
• 1990 as MCMXC (The title of musical project Enigma's debut album MCMXC a.D., named after the year of its release.)
• 2014 as MMXIV - the year of the games of the XXII (22nd) Olympic Winter Games (in Sochi)

So the first problem to address is convert from digits from 1 - 10 to roman numerals. Since the ASCII coding table does not code for roman numerals, i.e, there is no direct mapping from digits to roman numerals, we must convert the manually. 

The second issue is to handle when the digit equals to 4 or 9, we must process it separately. 

Solution:
Based on the analysis above, the straight-forward solution is to parse the integer and get the digit and place value one-by-one. There are two ways to parse the integer, one is from right to left while the other is from left to right. In this problem, I choose left to right since append the string as tail is much efficient than append at head. Then we convert the digit into roman numeral and append it to the string. 

Code (Java):

public class Solution {
    public String intToRoman(int num) {
        if (num <= 10) return toString(num);
        
        // we first get the num of digits of the integer
        int temp = num;
        int nDigits = -1; // 1 less than actual number
        while (temp > 0) {
            nDigits++;
            temp /= 10;
        }
        
        // create an empty string
        StringBuilder sb = new StringBuilder();
        
        // parse the integer from left to right
        while (num > 0) {
            int place = (int) Math.pow(10, nDigits--);
            int digit = num / place;
            num -= digit * place;
            
            if (digit == 4 || digit == 9) {
                sb.append(toString(place));
                sb.append(toString((digit + 1) * place));
            } else if (digit == 5) {
                sb.append(toString(place * digit));
            } else if (digit < 4){
                for (int i = 0; i < digit; i++) {
                    sb.append(toString(place));
                }
            } else if (digit > 5) {
                sb.append(toString(5 * place));
                for (int i = 0; i < digit - 5; i++) {
                    sb.append(toString(place));
                }
            }
        }
        
        return sb.toString();
    }
    
    private String toString(int num) {
        String roman = "";
        switch(num) {
            case 1: roman = "I";
                    break;
            case 2: roman = "II";
                    break;
            case 3: roman = "III";
                    break;
            case 4: roman = "IV";
                    break;
            case 5: roman = "V";
                    break;
            case 6: roman = "VI";
                    break;
            case 7: roman = "VII";
                    break;
            case 8: roman = "VIII";
                    break;
            case 9: roman = "IX";
                    break;
            case 10: roman = "X";
                     break;
            case 50: roman = "L";
                     break;
            case 100: roman = "C";
                      break;
            case 500: roman = "D";
                      break;
            case 1000: roman = "M";
                       break;
            default: roman = "Invalid";
                     break;
        }
        return roman;
    }
}

A Neat Solution:
We can see that the crux of the solution above is to handle while digit < 4, digit = 4, digit = 5, digit > 5, digit = 9. There is a very neat solution below that does not need to handle those cases:

public class Solution {
    public String intToRoman(int num) {
        String[] str = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int[] val = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < val.length; i++) {
            while (num >= val[i]) {
                num -= val[i];
                sb.append(str[i]);
            }
        }
        return sb.toString();
    }
}

Summary:

The problem itself is not hard at all, but requires carefully handling all the corner cases. The second solution is very tricky but the code is neat. Make sure you understand it.