C++ solution using algorithm to compute value - 28ms


  • 0
    A

    I have only used legal roman numbers and corresponding values and applied algorithm to compute the roman string.
    The algorithm is pretty simple to understand and uses computational logic to calculate the value rather than getting it from pre-computed arrays.

    class Solution {
    public:
        string intToRoman(int num) {
            string res; // output string.
            
            // List of roman numbers and their corresponding values.
            char romanChar[7] = {'M', 'D', 'C', 'L', 'X', 'V', 'I'};
            int values[7] = {1000, 500, 100, 50, 10, 5, 1};
            
            // ptr is used to keep track of roman value in above 2 arrays.
            int ptr = 0;
            
            // Continue the loop until num is greater than zero. 
            // Start from larger number and then keep on substracting.
            while (num > 0 && ptr < 7)
            {
                // To check if number is 9, 90, 900. In this case we represent roman number as "IX", "XC", "CM".
                // Note that difference between index of roman values is 2. Therefore we have used romanChar[ptr + 1] romanChar[ptr - 1]
                // (((ptr+1) % 2) == 0) condition takes care that we only check this for 1, 10, 100, 1000.
                // (ptr < 6) avoids overflow
                if ((ptr < 6) && ((num / values[ptr + 1]) == 9) && (((ptr+1) % 2) == 0))
                {
                    res.push_back(romanChar[ptr + 1]);
                    res.push_back(romanChar[ptr - 1]);
    
                    // Substracting the value from number
                    num -= 9 * values[ptr + 1];
                }
                else 
                {
                    int count = num / values[ptr];
                    
                    if (count == 4)
                    {
                        res.push_back(romanChar[ptr]);
                        res.push_back(romanChar[ptr - 1]);
                    }
                    else
                    {
                        for (int i = 0 ; i < count; i++)
                            res.push_back(romanChar[ptr]);
                    }
                    // Substracting the value from number
                    num -= count * values[ptr];
                }
                ptr++;
            }
            
            return res;
        }
    };
    

    Note: If someone comes up with a better condition for (((ptr+1) % 2) == 0) kindly let me know. I am not completely happy with this condition.


Log in to reply
 

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