Integer To Roman - Leetcode Solution

Problem description:

Given an integer, convert it to a roman numeral.

Example 1:

Input: num = 3 Output: "III"

Example 2:

Input: num = 4 Output: "IV"

Example 3:

Input: num = 9 Output: "IX"

Example 4:

Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution approach:

The problem can be solved using a greedy approach, where we keep subtracting the maximum possible value of a roman numeral from the given number and add its corresponding roman numeral to the result string until the number becomes 0.

To implement this approach, we can create a mapping of integers to their corresponding roman numerals. We can then iterate over the mapping in descending order and check if the current integer value is less than or equal to the given number. If it is, we add the corresponding roman numeral to the result string and subtract the integer value from the given number. We repeat this process until the given number becomes 0.

Solution in Python:

class Solution: def intToRoman(self, num: int) -> str: # Mapping of integers to their corresponding roman numerals mapping = { 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' }

    # Result string
    result = ''
    
    # Iterate over the mapping in descending order
    for integer, roman in mapping.items():
        # Check if the current integer value is less than or equal to the given number
        while num >= integer:
            # Add the corresponding roman numeral to the result string and subtract the integer value from the given number
            result += roman
            num -= integer
            
    # Return the result string
    return result

This solution has a time complexity of O(1), as we are iterating over a fixed number of integers, and a space complexity of O(1), as we are only using a fixed number of variables.

1