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 = ""
        i = 0
        while num > 0:
            count = num // val[i]
            roman += syms[i] * count
            num -= val[i] * count
            i += 1
        return roman
      

class Solution {
public:
    string intToRoman(int num) {
        vector<int> vals = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector<string> syms = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        string roman = "";
        for (int i = 0; i < vals.size(); ++i) {
            while (num >= vals[i]) {
                roman += syms[i];
                num -= vals[i];
            }
        }
        return roman;
    }
};
      

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

var intToRoman = function(num) {
    const vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1];
    const syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"];
    let roman = '';
    for (let i = 0; i < vals.length; i++) {
        while (num >= vals[i]) {
            roman += syms[i];
            num -= vals[i];
        }
    }
    return roman;
};
      

Problem Description

You are given an integer num between 1 and 3999, inclusive. Your task is to convert this integer into its corresponding Roman numeral representation and return it as a string.

• Roman numerals are represented by seven different symbols: I (1), V (5), X (10), L (50), C (100), D (500), and M (1000).
• Roman numerals are usually written largest to smallest from left to right. However, to avoid four characters being repeated in succession, certain numbers are written using subtraction (for example, 4 is IV instead of IIII).
• Each integer input has exactly one valid Roman numeral representation. You do not need to handle invalid input or ambiguous cases.

Thought Process

The first step is to understand how Roman numerals work and how to map values to their symbols. A naive approach might be to build the numeral digit by digit, but because of special cases (like 4 = IV, 9 = IX, etc.), we need to account for these subtractive combinations.

Instead of trying to build the numeral from individual digits, it's easier to work from the largest possible values down to the smallest, always subtracting as much as we can and appending the corresponding symbols. This "greedy" approach ensures we always use the largest symbol possible at each step, which matches the rules of Roman numeral construction.

By listing out all the possible symbol-value pairs (including subtractive cases like CM for 900 and IV for 4), we can process the integer in a straightforward loop, reducing the number and building the result string as we go.

Solution Approach

We use a greedy algorithm to convert the integer to a Roman numeral. Here's the step-by-step plan:

1. Prepare value-symbol pairs:
   • Create two lists: one for the integer values, and one for their corresponding Roman numeral symbols.
   • Order both lists from largest to smallest, and include subtractive combinations (like 900, 400, 90, etc.) before their respective base values.
2. Iterate through the value-symbol pairs:
   • For each value, check how many times it fits into the current number (num).
   • Append the corresponding symbol that many times to the result string.
   • Reduce num by the value multiplied by the count.
   • Continue to the next value until num becomes zero.
3. Return the result:
   • The constructed string is the Roman numeral representation.

This approach is efficient because it always uses the largest possible symbols first, and the list of value-symbol pairs is fixed and small, making the loop very fast.

Example Walkthrough

Let's walk through the process for num = 58:

1. Start with num = 58. The largest value less than or equal to 58 is 50 (L).
   • 58 / 50 = 1 (use L once)
   • Append L to the result. Remaining num = 58 - 50 = 8.
2. Next, 40 (XL) is too big. Move to 10 (X), which is also too big. Move to 9 (IX), still too big. Next is 5 (V).
   • 8 / 5 = 1 (use V once)
   • Append V to the result. Remaining num = 8 - 5 = 3.
3. Next, 4 (IV) is too big. Next is 1 (I).
   • 3 / 1 = 3 (use I three times)
   • Append III to the result. Remaining num = 0.
4. The result is LVIII.

This matches the expected Roman numeral for 58.

Time and Space Complexity

Brute-force approach: If you tried to process each digit individually and handled all rules with many conditionals, the code would be longer and less efficient, but still O(1) because the input range is fixed.

Optimized approach (ours):

• Time Complexity: O(1). The number of iterations is bounded by the number of value-symbol pairs (13), and the input is limited (1 to 3999), so the work done does not grow with the input.
• Space Complexity: O(1). We only use a fixed number of variables and arrays (no data structures that grow with input).

Summary

To convert an integer to a Roman numeral, we use a greedy approach: always subtract the largest possible Roman value and append its symbol, handling both standard and subtractive cases. This method is efficient, simple, and leverages the structure of Roman numerals. The solution is elegant because it reduces the problem to a series of simple, repeatable steps using a small, fixed mapping of values to symbols.