all articles

leetcode war 12 - Integer to Roman

2017-09-19 @sunderls

leetCode js

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

Given an integer, convert it to a roman numeral.

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

first, what is roman numbers

I know what it is, but don't remember the detailed spec.

here is wikipedia link

symbol I V X L C D M
value 1 5 10 50 100 500 1000

attention to the subtractive notation, for 4 and 9:

symbo IV IX XL XC CD CM
value 4 9 40 90 400 900

seems simple, right?

trial 1 - check mod with 4 and 9

var intToRoman = function(num) {
    var result = [];
    var pace = 1000;
    var tmp = 0;

    var chars = {
        '1': 'I',
        '5': 'V',
        '10': 'X',
        '50': 'L',
        '100': 'C',
        '500': 'D',
        '1000': 'M'
    };

    while (num > 0) {
        tmp = Math.floor(num / pace);

        if (tmp > 0) {
            if (tmp < 4) {
                for (var i = 1; i <= tmp; i++) {
                    result.push(chars[pace]);                    
                }
            } else if (tmp === 4) {
                result.push(chars[pace]);
                result.push(chars[(tmp + 1) * pace]);
            } else if (tmp === 5) {
                result.push(chars[tmp * pace]);
            } else if (tmp < 9) {
                result.push(chars[5 * pace]);
                for (var i = 6; i <= tmp; i++) {
                    result.push(chars[pace]);                    
                }
            } else if (tmp === 9) {
                result.push(chars[pace]);
                result.push(chars[(tmp + 1) * pace]);
            }
        }

        num = num % pace;
        pace /= 10;
    }

    return result.join('');

};

accepted, but very slow. how can we do better?