Leetcode 12 Solution

This article provides solution to leetcode question 12 (integer-to-roman)
Categories:
Tags:
Access this page by simply typing in "lcs 12" in your browser address bar if you have bunnylol configured.

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

Thinking Process

The challenge part of this question is these three rules:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

You can definitely write special logic to handle them. But a much simpler way would be to include them in the symbol list:

Symbol       Value
I             1
IV            4
V             5
IX            9
X             10
XL            40
L             50
XC            90
C             100
CD            400
D             500
CM            900
M             1000

After that, we can just try to grab the largest symbol from the list to make the target number. For example, if the target number is 45, we grab a XL first, and then 5 is left, we grab a V. The result is XLV.

Time & Space Complexity

Assuming N is the bit length of the input number

  • Time complexity: O(n)
  • Space complexity: O(1)

Solution

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> a;
        a.push_back(make_pair(1000, "M"));
        a.push_back(make_pair(900, "CM"));
        a.push_back(make_pair(500, "D"));
        a.push_back(make_pair(400, "CD"));
        a.push_back(make_pair(100, "C"));
        a.push_back(make_pair(90, "XC"));
        a.push_back(make_pair(50, "L"));
        a.push_back(make_pair(40, "XL"));
        a.push_back(make_pair(10, "X"));
        a.push_back(make_pair(9, "IX"));
        a.push_back(make_pair(5, "V"));
        a.push_back(make_pair(4, "IV"));
        a.push_back(make_pair(1, "I"));

        string res;
        while (num)
        {
            for (int i = 0; i < a.size(); i++)
            {
                int cnt = num / a[i].first;
                if (cnt == 0)
                    continue;

                for (int j = 0; j < cnt; j++)
                    res += a[i].second;
                num -= cnt * a[i].first;
                break;
            }
        }

        return res;
    }
};