LeetCode 12. Integer to Roman

Description

https://leetcode.com/problems/integer-to-roman/

Given an integer, convert it to a roman numeral.

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

Explanation

The problem is about writing a function to convert an Arabic number to a Roman number.

We need to have some basic knowledge about Roman numerals.

Roman numerals, as used today, are based on seven symbols:

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

Numbers are formed by combining symbols and adding the values. Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX), a subtractive notation is used: as in this table:

Number	4	9	40	90	400	900
Notation	IV	IX	XL	XC	CD	CM

• I placed before V or X indicates one less, so four is IV (one less than five) and nine is IX (one less than ten)
• X placed before L or C indicates ten less, so forty is XL (ten less than fifty) and ninety is XC (ten less than a hundred)
• C placed before D or M indicates a hundred less, so four hundred is CD (a hundred less than five hundred) and nine hundred is CM (a hundred less than a thousand)

We build two arrays with the same length to solve the problem. One is storing values; the other one is storing Roman characters. Two arrays should have the same number at same index positions.

We develop our algorithms based on Roman subtractive method. Every time we subtract a value from input number, we add related Roman character to the result string.

Video Tutorial

Java Solution

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