Given an integer, convert it to a roman numeral.

The number is guaranteed to be within the range from 1 to 3999.

What is Roman Numeral?

• https://en.wikipedia.org/wiki/Roman_numerals
• https://zh.wikipedia.org/wiki/%E7%BD%97%E9%A9%AC%E6%95%B0%E5%AD%97
• http://baike.baidu.com/view/42061.htm

4 -> IV

12 -> XII

21 -> XXI

99 -> XCIX

1. Create a mapping between the roman symbols and their integer values. 

2. Starting from the biggest symbol, check the number of this symbol needed 

to construct the input integer. Add this many symbols to the result string builder if needed.

Subtract the added value from the input integer.

3. Proceed to the next biggest symbol and repeat step 2 until the input integer becomes 0.

 1 public class Solution {
 2     public String intToRoman(int num) {
 3         if(num <= 0) {
 4             return "";
 5         }
 6         int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
 7         String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
 8         StringBuilder res = new StringBuilder();
 9         int digit  = 0;
10         while (num > 0) {
11             int times = num / nums[digit];
12             num -= nums[digit] * times;
13             for ( ; times > 0; times--) {
14                 res.append(symbols[digit]);
15             }
16             digit++;
17         }
18         return res.toString();
19     }
20 }

Related Problems

Roman to Integer 

Integer to English