12. Integer to Roman

Intuition

Roman numerals are formed by appending symbols based on specific rules:

• If the value does not start with 4 or 9, symbols are selected from highest to lowest value.
• Subtractive forms (e.g., IV for 4, IX for 9) are used for certain combinations.
• There are limitations on consecutive use of symbols (e.g., I, X, C, M can appear at most 3 times).

Approach

1. Define Symbols and Values: - Create arrays or mappings for Roman numeral symbols and their corresponding values.
2. Iterative Conversion: - Iterate through the predefined symbols and values. - While the input number is greater than or equal to the current value: - Append the corresponding symbol to the result. - Subtract the value from the input number.
3. Subtractive Forms: - Include predefined subtractive forms (e.g., IV, IX) for specific values.
4. Return Result: - Convert the constructed list or string of symbols into the final Roman numeral representation.

Complexity

Time Complexity:

O(1) since the maximum number of iterations is limited by the number of predefined symbols and their values.

Space Complexity:

O(1) for the same reason, as the space used does not scale with the size of the input.

This approach ensures that the conversion from an integer to its Roman numeral representation follows the rules provided efficiently and correctly.

Code

C++

class Solution {
public:
    string intToRoman(int num) {
        map values = 
        {{1,"I"},{4,"IV"},{5,"V"},{9,"IX"},{10,"X"},{40,"XL"},{50,"L"},{90,"XC"},{100,"C"},{400,"CD"},{500,"D"},             {900,"CM"},{1000,"M"}};
        
        string res;
        
        map::reverse_iterator it;
        for (it = values.rbegin(); it != values.rend(); it++){
            while(num>=it->first){
                res+=it->second;
                num-=it->first;
            }
        }
        return res;
    }
};

Python

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        
        result = []
        
        for i in range(len(values)):
            while num >= values[i]:
                num -= values[i]
                result.append(symbols[i])
        
        return ''.join(result)

Java

class Solution {
    public String intToRoman(int num) {
        String ones[] = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
        String tens[] = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
        String hrns[] = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
        String ths[] = { "", "M", "MM", "MMM" };

        return ths[num / 1000] + hrns[(num % 1000) / 100] + tens[(num % 100) / 10] + ones[num % 10];
    }
}

JavaScript

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
     const romanNum = {
    V̆̈: 5000,
    M: 1000,
    CM: 900,
    D: 500,
    CD: 400,
    C: 100,
    XC: 90,
    L: 50,
    XL: 40,
    X: 10,
    IX: 9,
    V: 5,
    IV: 4,
    I: 1,
  }
  var str = ''
   for (var i of Object.keys(romanNum)) {
    var q = Math.floor(num / romanNum[i])
    num -= q * romanNum[i]
    str += i.repeat(q)
  }
  return str
};