A solution by following the rules of Roman numerical system


  • 0
    C

    unlike the fastest solution which uses a table for all the valid combinations in every tens, e.g. 10, 20, 30, ..., this solution tries to construct the roman representation following the original rules of the number system from wikipedia. Hopefully it is correctly implemented. It's still reasonably quick and can be easily extended for larger radix/alphabet for, say 5000, 10000, 50000, etc.

    class Solution {
    public:
        string intToRoman(int num) {
            const vector<int> radix {1000, 500, 100, 50, 10, 5, 1};
            const string alphabet = "MDCLXVI";
            ostringstream roman;
            
            for (int i = 0; i < radix.size(); i += 2)
                while (radix[i] <= num)
                {
                    const int factor = num / radix[i];
                    if (factor == 9)
                        roman << alphabet[i] << alphabet[i - 2];
                    else if (factor > 4)
                        roman << alphabet[i - 1];
                    else if (factor == 4)
                        roman << alphabet[i] << alphabet[i - 1];
                    else
                        roman << string(factor, alphabet[i]);
                    num -= (4 < factor && factor < 9) ? radix[i - 1] : factor * radix[i];
                }
            
            return roman.str();
        }
    };

Log in to reply
 

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