Integer To Roman

String Math

Problem

Given an integer, convert it to a roman numeral.

The input number will be between 1<= num <= 3199

For example:

Input: num = 3
Output: "III"

Input: num = 4
Output: "IV"

Input: num = 9
Output: "IX"

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

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

Thought Process

• How do we know which digit position we are at?

  • We know which digit position we are in by modding and dividing with either 1000, 100, or 10. Why it's only these numbers is because our input number will only go to the thousands place.

• How can we convert, like, an 8 to VIII or an 80 to LXXX?

  • By having an array of roman numerals that are mapped/placed in their corresponding digit positon

• To solve this question, we have to pay attention to the digit positions.

• Each digit position will map to a corresponding roman numeral in that specific digit positoin. This way to convert the number to it's roman numeral equivalenet, we will divide the input number by each digit position to get the correct roman numeral mapping.

Solution

class Solution:
    def intToRoman(self, num: int) -> str:
        number = str(num)
        res = ""
        thousand = ["", "M", "MM","MMM"]
        hundred = ["", "C", "CC", "CCC","CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["","X", "XX", "XXX", "XL", "L","LX","LXX", "LXXX", "XC", "XIX","XX"]
        ones = ["","I","II","III","IV","V","VI","VII","VIII","IX","X"]
        
        res = thousand[num // 1000] + hundred[(num%1000)//100] + tens[(num%100)//10] + ones[num%10]
        
        return res
        

Key Facts

• We are mapping the corresponding digit positions to their roman numeral equivalent

  • d

• We can get a hold of the corresponding roman numeral equicalent of the digit postion by modding and dividing.

  • Mod any number by 10 and you will get the ones/digit position. Mod any 1000 number by 1000 you and will get the 100 position, etc.

  • We can utilize this for each 1000, 100, 10, and 1's digit position

Time Complexity

• Time: $O(n)$

• Space: $O(n)$ since we have arrays of roman numerals