deepSWE.io

Integer to Roman

MathString

MediumLeetCode #12

15 min

Problem Statement

Given an integer, convert it to a roman numeral.

Example

Example 1:

Input: num = 58

58LVIII

Output: "LVIII"

Explanation: L = 50, V = 5, III = 3.

Solution (Greedy Approach)

The most straightforward way to convert an integer to a Roman numeral is to use a greedy approach. We can predefine the Roman numeral symbols and their corresponding integer values, from largest to smallest.

Algorithm Steps

Create two arrays, one for integer values and one for the corresponding Roman symbols. Order them from largest to smallest.
Initialize an empty string to build the Roman numeral.
Loop through the values array. For each value, check how many times it can be subtracted from the input number.
Append the corresponding Roman symbol to the result string for each subtraction.
Update the input number by subtracting the value.
Continue until the input number becomes 0.

Input (number):

Remaining Number

Roman Numeral

Start with number = 58.

Integer to Roman Solution


class Solution:
    def intToRoman(self, num: int) -> str:
        val = [
            1000, 900, 500, 400,
            100, 90, 50, 40,
            10, 9, 5, 4,
            1
            ]
        syb = [
            "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 += syb[i]
                num -= val[i]
            i += 1
        return roman_num