Problem Statement in English

You’re given an integer num. Convert it to a roman numeral and return a string representing the roman numeral.

Approach

We can approach this problem by storing the integer values and their corresponding roman numeral representations in a list.

We can then iterate through this list, subtracting the integer values that are less than or equal to the current digit of the input number and appending the corresponding roman numeral to the result string until the input number is reduced to zero.

And we’re done!

Solution in Python


class Solution:
    def intToRoman(self, num: int) -> str:
        roman = ""
        storeIntRoman = [[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"]]
        
        for i in range(len(storeIntRoman)):
            while num >= storeIntRoman[i][0]:
                roman += storeIntRoman[i][1]
                num -= storeIntRoman[i][0]
                
        return roman

Complexity

  • Time: $O(1)$
    Since the maximum value of num is 3999, the number of iterations will be constant and will not depend on the input size.

  • Space: $O(1)$

  • Since the output string will have a maximum length of 15 characters (for the number 3888, which is “MMMDCCCLXXXVIII”), the space used for the output string is also constant and does not depend on the input size.

Mistakes I Made

My solution was overcomplicated and nowhere as elegant as this.

And we are done.