Elegant solution without hardcoding


  • 0
    F

    Roman numerals are composed of I:1, V:5, X:10, L:50, C:100, D:500, M:1000. Decimal to roman conversion is simple if we observe that each decimal place has it's own representation in the final numeral, which is independent of other places. So 99 is not IC(100 - 1), instead it is XCIX(90 + 9) (XC for 90, IX for 9).

    Thus, now our task is to break the number down to digits and represent each digit, depending on place value, and then just concatenate them.

    Conversion of each digit follows the same pattern as follows. Given a power p of 10, it has it's '1', '5' and '10'. The numbers are in quotes because these letters can change but the overall number will follow the same pattern. Take the units digit, for example. The '1' for units digit is I(decimal 1), '5' -> 'V'(decimal 5), '10' -> 'X'(decimal 10). Similarly, for the tens(10) digit, the corresponding letters are '1' -> 'X'(1 * 10), '5' -> 'L'(5 * 10), '10' -> 'C' (10 * 10). Hence the multiplier is given by d's place value.

    Finally, note the pattern. 4 and 9 are IV and IX resp (similarly 40, 90 are XL, XC resp. and so on). For others, it would be '0' or '5' + number of ones. So 3 is III(300 is CCC), 7 is VII(70 is LXX), and so on.

    Thus, in the final code we take each digit of the original number, and get the representation by sending the array of '1', '5', and '10' based on the place value to the repr function.

    Note: Since the loop goes from units to tens to hundreds to thou, the new repr strings should be prepended to the original, not appended.
    Note: Representation of 0 at any place is an empty string.

    class Solution {
        // Representation of d of given place value
        string repr(int d, char *romans) {        
            string ret = "";
            if (d == 4 || d == 9) // 4 => IV, 9 => IX
                ret = {romans[0], romans[(d == 4) ? 1 : 2]};
            else {
                // Otherwise it's [V] + I[II]
                if (d >= 5) {
                    ret.push_back(romans[1]); d -= 5;
                }
                while (d--)
                    ret.push_back(romans[0]);
            }
            return ret;
        }
    public:
        string intToRoman(int num) {
            // Blanks just to ensure no invalid memory accesses. Because
            // 1 <= num <= 3999, those indices won't be accessed anyway
            char romans[] = {'I', 'V', 'X', 'L', 'C', 'D', 'M', ' ', ' '};
            int d, pos = 0;
            string rom = "";
            
            while (num) {
                d = num % 10; num /= 10;
                rom.insert(0, repr(d, romans + pos));
                pos += 2;
            }
            
            return rom;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.