LeetCode Problem

Problem Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

Examples

Input: 3
Output: III

Input: 4
Output: IV

Constraints

1 <= num <= 3999

Follow-up

Approach to Solve

Use a greedy algorithm to convert the integer to Roman numeral.

Code Implementation

class Solution:
    def intToRoman(self, num: int) -> str:
        val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman_num = ''
        i = 0
        while num > 0:
            for _ in range(num // val[i]):
                roman_num += syms[i]
                num -= val[i]
            i += 1
        return roman_num

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder roman = new StringBuilder();
        for (int i = 0; i < values.length && num > 0; i++) {
            while (num >= values[i]) {
                num -= values[i];
                roman.append(symbols[i]);
            }
        }
        return roman.toString();
    }
}

class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int, string>> values = {{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] : values) {
            while (num >= value) {
                result += symbol;
                num -= value;
            }
        }
        return result;
    }
};

Explanation

The Integer to Roman problem is solved using a greedy algorithm. Here's a detailed explanation of the approach:

We define two arrays: one for integer values and another for their corresponding Roman numeral symbols. These arrays are sorted in descending order of value.
The integer values include not just the base Roman numeral values (1000, 500, 100, 50, 10, 5, 1) but also the subtractive combinations (900, 400, 90, 40, 9, 4). This allows us to handle cases like 4 (IV) and 9 (IX) directly.
We iterate through these arrays from largest to smallest value: a. While the input number is greater than or equal to the current value, we append the corresponding symbol to our result string and subtract the value from the input number. b. We continue this process until we've processed the entire input number.
This greedy approach works because Roman numerals follow a largest-to-smallest pattern, with special cases for the subtractive combinations.

For example, to convert 1994 to Roman numerals:

First, we add 'M' (1000), leaving 994
Then 'CM' (900), leaving 94
Then 'XC' (90), leaving 4
Finally 'IV' (4)
The result is 'MCMXCIV'

Time Complexity: O(1) because there's a finite set of Roman numeral symbols, and the largest number is 3999. Space Complexity: O(1) as we're using a fixed amount of extra space regardless of the input.

This approach is efficient and straightforward, making it an optimal solution for converting integers to Roman numerals within the given constraints.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)