MEDIUM

Integer to Roman

Given an integer, convert it to a roman numeral.

Example

Input:

num = 1994

Output:

"MCMXCIV"

Explanation:
1994 = M + CM + XC + IV

Constraints

1 ≤ num ≤ 3999

Solution: Greedy

Time Complexity: O(1), since the number is limited to 3999 and the number of symbols is constant.
Space Complexity: O(1), as only a constant amount of extra space is used.

C++

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> valueSymbols = {
            {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
            {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
            {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
        };
        string result;
        for (const auto& [value, symbol] : valueSymbols) {
            while (num >= value) {
                result += symbol;
                num -= value;
            }
        }
        return result;
    }
};